Coral reefs are home to the greatest diversity of marine life, and many species on reefs live in symbiotic associations. Studying the historical biogeography of symbiotic species is key to unravelling (potential) coevolutionary processes and explaining species richness patterns. Coral-dwelling gall crabs (Cryptochiridae) live in obligate symbiosis with a scleractinian host, and are ideally suited to study the evolutionary history between heterogeneous taxa involved in a symbiotic relationship. The genus Opecarcinus Kropp and Manning, 1987, like its host coral family Agariciidae, occurs in both Indo-Pacific and Caribbean seas, and is the only cryptochirid genus with a circumtropical distribution. Here, we use mitochondrial and nuclear DNA gene fragments of Opecarcinus specimens sampled from 21 Indo-Pacific localities and one Atlantic (Caribbean) locality. We applied several species delimitation tests to characterise species diversity, inferred a Bayesian molecular-clock time-calibrated phylogeny to estimate divergence times and performed an ancestral area reconstruction. Time to the most recent common ancestor (tMRCA) of Opecarcinus is estimated at 15−6 Mya (middle Miocene—late Miocene). The genus harbours ~ 15 undescribed species as well as several potential species complexes. There are indications of strict host-specificity patterns in certain Opecarcinus species in the Indo-Pacific and Atlantic, however, a robust phylogeny reconstruction of Agariciidae corals—needed to test this further—is currently lacking. The Indo-West Pacific was inferred to be the most probable ancestral area, from where the Opecarcinus lineage colonised the Western Atlantic and subsequently speciated into O. hypostegus. Opecarcinus likely invaded from the Indo-West Pacific across the East Pacific Barrier to the Atlantic, before the full closure of the Isthmus of Panama. The subsequent speciation of O. hypostegus, is possibly associated with newly available niches in the Caribbean, in combination with genetic isolation following the closure of the Panama Isthmus.