The fairy wrasses (genus Cirrhilabrus) are among the most captivating and 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 the evolutionary relationships using molecular and morphological data have largely been unsuccessful. Here we use a phylogenomic analysis of 991 ultraconserved elements (UCEs) and mitochondrial COI to uncover the evolutionary history and patterns of temporal and spatial diversification of the fairy wrasses. We find that analyses of concatenated sequences confidently resolve the major relationships of Cirrhilabrus. Our analyses of phylogenetic signal suggest that extensive gene-tree incongruence is primarily caused by estimation error rather than incomplete lineage sorting, leading to poor phylogenetic resolution in a summary-coalescent analysis of the data. 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. 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 sustained 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, in a phylogenetically recalcitrant group of fishes.