The nutritional stress hypothesis explains how learned features of song, such as complexity and local dialect structure, can serve as indicators of male quality of interest to females in mate choice. The link between song and quality comes about because the brain structures underlying song learning largely develop during the first few months post-hatching. During this same period, songbirds are likely to be subject to nutritional and other stresses. Only individuals faring well in the face of stress are able to invest the resources in brain development necessary to optimize song learning. Learned features of song thus become reliable indicators of male quality, with reliability maintained by the developmental costs of song. We review the background and assumptions of the nutritional stress hypothesis, and present new experimental data demonstrating an effect of nestling nutrition on nestling growth, brain development, and song learning, providing support for a key prediction of the hypothesis.