Cirrhilabrus wakanda sp. nov. is described on the basis of the holotype and four paratypes collected between 50 and 80m depth over low-complexity reef and rubble bottoms at the east coast of Zanzibar, Tanzania, Africa. The new species belongs to a group of fairy wrasses from the western Indian Ocean, sharing a combination of characters that include: short pelvic fins (not or barely reaching anal-fin ori- gin); relatively unmarked dorsal and anal fins; males with a strongly lanceolate caudal fin (except in C. rubrisquamis); both sexes with a pair of prominent facial stripes above and below the orbit; and both sexes with prominent purple scales and osseus elements that persist, and stain purple, respectively, even in preservation. This group of fairy wrasse is part of a larger complex that includes related species from the western Pacific Ocean. In addition to meristic and morphometric comparisons, we also compare mitochondrial DNA sequence data to the aforementioned, putatively related species.