The present review discusses whether sexual selection for complex songs modified brain structures in songbirds. If producing complex song is costly in males, song complexity should be correlated with some indexes of brain structures. At the same time, if selecting a potent mate based on song is costly in females, they also should develop some brain specializations correlated with the cognitive effort. Most existing studies focused on the volume of song control nuclei and song behavior. There are two main pathways for song control in the songbird brain: the posterior pathway that directly controls song production and the anterior pathway related with song perception. For the posterior pathway, between-species comparisons found positive correlations between the volume and behavior in males. However, most within-species comparisons failed to find such correlations. Several studies examined the relationship between song perception and the anterior pathway and lesion studies showed reduced selectivity for song in both males and females. Song selectivity and the volume of anterior pathway were positively correlated in females. Taken together, data are equivocal for the production part, but more consistent for the perception part. To study further the relationship between brain evolution and sexual selection in birdsong, methods for measuring song complexity need to be refined and other anatomical indexes besides volumetric methods should be examined.