For most vertebrates, sexual fate is genetically determined and remains fixed throughout life. However, for some teleost fishes sex is more plastic. Significant progress has been made in characterising the cellular and molecular processes that underpin gonadal sex change. The brain-mediated mechanisms that underlie and initiate this transformation, however, remain poorly understood. One reason for this is the current lack of a neuroanatomical reference work for sex changing fishes. Here, we present a brain atlas for the New Zealand (NZ) spotty wrasse (Notolabrus celidotus), developed from 10 wild caught specimens (2 male and 8 female). From each fish, coronal cryosections were collected and stained with cresyl violet solution. Photomicrographs were taken of each section using an inverted bright field microscope and 3D reconstructions were rendered of each brain for annotation and volumetric comparison of specific brain regions. The brain atlas describes the general features of the NZ spotty wrasse brain as well as its specificities. This atlas provides the necessary foundation for further investigation of the brain mechanisms driving protogyny in this species.