Interspecific associations may limit the dispersal of individual species, but may also facilitate it when entire co-evolved systems expand their geographic ranges. We tested the recent proposal that episodic land bridges linked Africa and Madagascar at three stages during the Cenozoic by comparing divergence estimates of Madagascar’s angiosperm taxa with their dispersal mechanisms. Plants that rely on gravity for seed dispersal indicate at least two episodes of land connection between Africa and Madagascar, in the Early Palaeocene and Early Oligocene. Seed dispersal by strepsirrhine primates possibly evolved in the Palaeocene, with the divergence of at least one endemic Malagasy angiosperm genus, Burasaia (Menispermaceae). This genus may have facilitated the lemur colonization of Madagascar. Frugivory, nectarivory and gummivory probably generalized in the Oligocene, with the co-evolution of modern lemurs and at least 10 new Malagasy angiosperm families. In the Late Miocene, more angiosperms were probably brought from Africa by birds via a discontinuous land connection, and radiated on Madagascar in diffuse association with birds (asities) and dwarf nocturnal lemurs (cheirogaleids). During the same connective episode, Madagascar was probably colonized by hippopotamuses, which both followed and re-seeded a variety of plants, forming the grassy Uapaca ‘tapia’ forest and ericoid ‘savoka’ thicket.