Mutualisms (cooperative interactions between species) have had a central role in the generation and maintenance of life on earth. Insects and plants are involved in diverse forms of mutualism. Here we review evolutionary features of three prominent insect-plant mutualisms: pollination, protection and seed dispersal. We focus on addressing five central phenomena: evolutionary origins and maintenance of mutualism; the evolution of mutualistic traits; the evolution of specialization and generalization; coevolutionary processes; and the existence of cheating. Several features uniting very diverse insect-plant mutualisms are identified and their evolutionary implications are discussed: the involvement of one mobile and one sedentary partner; natural selection on plant rewards; the existence of a continuum from specialization to generalization; and the ubiquity of cheating, particularly on the part of insects. Plant-insect mutualisms have apparently both arisen and been lost repeatedly. Many adaptive hypotheses have been proposed to explain these transitions, and it is unlikely that any one of them dominates across interactions differing so widely in natural history. Evolutionary theory has a potentially important, but as yet largely unfilled, role to play in explaining the origins, maintenance, breakdown and evolution of insect-plant mutualisms.