Identifying the proximate and ultimate causes that drive behavioral evolution is one of biology’s great challenges. Central to this effort is resolving the nature of genes important for behavior. We leverage the substantial natural variation observed in a courtship behavior amongst the Malawi cichlid adaptive radiation to do so. Males of up to 200 Malawi cichlid species build mating nests (bowers) out of sand for the purpose of attracting females. Two basic types of bowers exist: “pits” (depressions) and “castles” (mounds). Phylogenetic analyses indicate that pits are the likely ancestral form from which castles have repeatedly evolved, possibly more than a dozen times. We assayed the genetic basis of bower building by sequencing the genomes of 10 castle-building and 12 pit-digging species from diverse genera. Analyses of genetic differentiation indicate that >6,000 SNPs are perfectly fixed between pit and castle species. Genes associated with these variants (~1,400) are related by function and are involved in key neural processes such as axon guidance and glutamate signaling. Since the majority of variants fall in non-coding regions we investigated the role of cis-regulatory divergence by performing RNA-seq on whole brain samples from F1 hybrids of a castle-builder and a pit-digger. We calculated differential allele-specific expression (diffASE) genome-wide between animals engaged in bower building and animals kept in isolation. We find hundreds of genes that possess both significant regulatory divergence and behaviorally driven expression changes and that are associated with fixed SNPs. These genes show significant overlap with the functional categories identified above, indicating that the repeated evolution of a bower-building has been driven by polygenic cis-regulatory adaptation. Our findings suggest a new and unexpected mechanism through which behaviors may evolve and provide grounds for future mechanistic studies of the genes involved.