We show using the most complete phylogeny of one of the most species-rich orders of vertebrates (Gobiiformes), and calibrations from the rich fossil record of teleost fishes, that the genus Typhleotris, endemic to subterranean karst habitats in southwestern Madagascar, is the sister group to Milyeringa, endemic to similar subterranean systems in northwestern Australia. Both groups are eyeless, and our phylogenetic and biogeographic results show that these obligate cave fishes now found on opposite ends of the Indian Ocean (separated by nearly 7,000 km) are each others closest relatives and owe their origins to the break up of the southern supercontinent, Gondwana, at the end of the Cretaceous period. Trans-oceanic sister-group relationships are otherwise unknown between blind, cave-adapted vertebrates and our results provide an extraordinary case of Gondwanan vicariance.