The adaptive significance of human brain evolution has been frequently studied through comparisons with other primates. However, the evolution of increased brain size is not restricted to the human lineage but is a general characteristic of primate evolution. Whether or not these independent episodes of increased brain size share a common genetic basis is unclear. We sequenced and de novo assembled the transcriptome from the neocortical tissue of the most highly encephalized non-human primate, the tufted capuchin monkey (Cebus apella). Using this novel dataset, we conducted a genome-wide analysis of orthologous brain-expressed protein coding genes to identify evidence of conserved gene-phenotype associations and species-specific adaptations during three independent episodes of brain size increase. We identify a greater number of genes associated with either total brain mass or relative brain size across these 6 species than show species-specific accelerated rates of evolution in individual large-brained lineages. We test the robustness of these associations in an expanded dataset of 13 species, through permutation tests and by analyzing how genome-wide patterns of substitution co-vary with brain size. Many of the genes targeted by selection during brain expansion have glutamatergic functions or roles in cell cycle dynamics. We also identify accelerated evolution in a number of individual capuchin genes whose human orthologs are associated with human neuropsychiatric disorders. These findings demonstrate the value of phenotypically informed genome analyses, and suggest at least some aspects of human brain evolution have occurred through conserved gene-phenotype associations. Understanding these commonalities is essential for distinguishing human-specific selection events from general trends in brain evolution.