Halichoeres sazimai, n. sp. is described from the Western South Atlantic. During many years it was misidentified as H. bathyphilus from the Northwestern Atlantic, but it can be distinguished from the latter by striking color differences between the two species, with H. sazimai being characterized by a white body with a midline, zigzag patterned stripe on body, black and brownish in terminal males and yellow or golden in females and juveniles. Preserved specimens can also be distinguished by the visible mid-body stripe in H. sazimai, which disappears in H. bathyphilus. Diagnostic differences in the mitochondrial DNA cytochrome b gene separate H. sazimai from all other Western Atlantic labrids, with H. bathyphilus being its sister species. Individuals of H. sazimai were observed living on the deeper parts (20-40 m) of rocky reefs and sand bottoms, apparently associated with water temperatures lower than 18°C. This species is currently known from the southeastern and southern coasts of Brazil, from Espírito Santo to Santa Catarina States.