How, when, and from where Madagascar's vertebrates arrived on the island is poorly known, and a comprehensive explanation for the distribution of its organisms has yet to emerge. We begin to break that impasse by analyzing vertebrate arrival patterns implied by currently existing taxa. For each of 81 clades, we compiled arrival date, source, and ancestor type (obligate freshwater, terrestrial, facultative swimmer, or volant). We analyzed changes in arrival rates, with and without adjusting for clade extinction. Probability of successful transoceanic dispersal is negatively correlated with distance traveled and influenced by ocean currents and ancestor type. Obligate rafters show a decrease in probability of successful transoceanic dispersal from the Paleocene onward, reaching the lowest levels after the mid-Miocene. This finding is consistent with a paleoceanographic model [Ali JR, Huber M (2010) Nature 463:653-656] that predicts Early Cenozoic surface currents periodically conducive to rafting or swimming from Africa, followed by a reconfiguration to present-day flow 15-20 million years ago that significantly diminished the ability for transoceanic dispersal to Madagascar from the adjacent mainland.