The Arabian Sea is a heterogeneous region with high coral cover and warm stable conditions at the western end (Djibouti), in contrast to sparse coral cover, cooler temperatures, and upwelling at the eastern end (southern Oman). We tested for barriers to dispersal across this region (including the Gulf of Aden and Gulf of Oman), using mitochondrial DNA surveys of 11 reef fishes. Study species included seven taxa from six families with broad distributions across the Indo-Pacific and four species restricted to the Arabian Sea (and adjacent areas). Nine species showed no significant genetic partitions, indicating connectivity among contrasting environments spread across 2000 km. One butterflyfish (Chaetodon melannotus) and a snapper (Lutjanus kasmira) showed phylogenetic divergences of d = 0.008 and 0.048, respectively, possibly indicating cryptic species within these broadly distributed taxa. These genetic partitions at the western periphery of the Indo-Pacific reflect similar partitions recently discovered at the eastern periphery of the Indo-Pacific (the Hawaiian and the Marquesan Archipelagos), indicating that these disjunctive habitats at the ends of the range may serve as evolutionary incubators for coral reef organisms.