The fairy wrasses (genus Cirrhilabrus) are among the most successful of the extant wrasse lineages (Teleostei: Labridae), with their 61 species accounting for nearly 10% of the family. Although species complexes within the genus have been diagnosed on the basis of coloration patterns and synapomorphies, attempts to resolve evolutionary relationships among these groups using molecular and morphological data have largely been unsuccessful. Here we use a phylogenomic approach with a data set comprising 991 ultraconserved elements (UCEs) and mitochondrial COI to uncover the evolutionary history and patterns of temporal and spatial diversification of the fairy wrasses. Our analyses of phylogenetic signal suggest that most gene-tree incongruence is caused by estimation error, leading to poor resolution in a summary-coalescent analysis of the data. In contrast, analyses of concatenated sequences are able to resolve the major relationships of Cirrhilabrus. We determine the placements of species that were previously regarded as incertae sedis and find evidence for the nesting of Conniella, an unusual, monotypic genus, within Cirrhilabrus. Our relaxed-clock dating analysis indicates that the major divergences within the genus occurred around the Miocene-Pliocene boundary, followed by extensive cladogenesis of species complexes in the Pliocene-Pleistocene. Biogeographic reconstruction suggests that the fairy wrasses emerged within the Coral Triangle, with episodic fluctuations of sea levels during glacial cycles coinciding with shallow divergence events but providing few opportunities for more widespread dispersal. Our study demonstrates both the resolving power and limitations of UCEs across shallow timescales where there is substantial estimation error in individual gene trees.