Lying some 400 km off the coast of southeastern Africa, Madagascar is the world’s largest oceanic island. It has been in roughly the same position relative to its parent continent for 120 million years, and as a consequence its mammal fauna is unusual in composition, with a low number of major taxa but a high diversity at lower taxonomic levels. Among Madagascar’s native terrestrial mammals, only the orders Primates, Rodentia, Carnivora and Insectivora are represented (plus, until recently, the enigmatic and endemic Bibymalagasia, and Artiodactyla in the form of semiaquatic pygmy hippopotamuses). This reflects the fact that terrestrial mammals are notoriously poor over-water dispersers; yet at the same time the ancestors of all of Madagascar’s mammals had to have crossed a wide oceanic barrier to get to the island at various points during the Tertiary. Here I examine the palaeogeographic evidence for potential land bridge or ‘stepping-stone’ connections with adjacent continents from the Mesozoic through the Cenozoic, and review the fossil records and phylogenies of each of Madagascar’s mammalian groups in an attempt to estimate the minimum number of crossings necessary to produce the island’s current faunal composition. Probable monophyletic origins for each major group, and thus a smaller rather than a larger number of crossings of the Mozambique Channel, imply that this water barrier has acted as a powerful filter; so powerful that it is unclear whether any crossings would have been possible without some form of subaerial connection, however ephemeral, at least from time to time during the Tertiary. Clarification of how Madagascar’s terrestrial mammal fauna may have originated is thus as likely to emerge from the geology of the seafloor surrounding the island as it is to come from the fossil record or from the internal and external relationships of its various components.