The rich diversity of coral reef organisms is supported, at least in part, by the diversity of coral reef habitat. Some of the most habitat specialised fishes on coral reefs are obligate coral-dwelling gobies of the genus Gobiodon that inhabit a range of coral species, mostly of the genus Acropora. However, the role of this specialised pattern of habitat use in the evolution of coral-dwelling gobies is not well understood. Diversification of coral-dwelling gobies may be driven by the diversification of their host corals (cospeciation), or alternatively, diversification of these fishes may have occurred independently of the diversification of host corals. The cospeciation hypothesis assumes similar timing in evolution of the gobies and their host corals. We used four genes for each group and the available fossil records to reconstruct and date phylogenies for 20 species of Gobiodon from the Indo-Pacific and the Red Sea, and for 28 species of the coral genus Acropora. Our results indicate that Gobiodon diversified mostly in the last ∼5 My, whereas Acropora corals have consistently diversified since the Eocene, making the hypothesis of cospeciation untenable. The fully resolved molecular phylogeny of the genus Gobiodon is in part at odds with previous analyses incorporating morphological data and indicates that some morphological traits form paraphyletic clades within Gobiodon. Our phylogeny supports a hypothesis in which Gobiodon diversified in the Indo-Pacific Ocean and then radiated recently, with multiple new variants found in the Red Sea.