A new species of labrid fish, the Sunset Fairy-wrasse, Cirrhilabrus greeni n. sp., is described from seven specimens, 39.4–47.3 mm SL, collected from the eastern Timor Sea, Northern Territory, Australia. The species is clearly distinguished by its terminal-phase male color pattern, consisting of pink to reddish hues on the upper half of the head and body and yellow on the lower half, in combination with a mainly yellow-orange dorsal fin and a scarlet-red anal fin. The caudal fin of the male is particularly distinctive, being emarginate but appearing lunate due to a clear central portion and tapering red bands along dorsal and ventral margins. Females can be distinguished from sympatric congeners by having a large black spot on the upper caudal peduncle. Sequencing of the mtDNA-barcode marker COI reveals that the new species has identical sequences to C. rubripinnis and C. aff. tonozukai from the Philippines, which have very different color patterns and tail shapes from the new species, indicating the new species has diverged recently and/or there is historic or episodic hybridization within the species complex.