Bird song is a sexually selected trait and females have been shown to prefer males that sing more complex songs. However, for repertoire size to be an honest signal of male quality it must be associated with some form of cost. This experiment investigates the effects of food restriction and social status during development on song complexity in the European starling (Sturnus vulgaris). Birds that experienced an unpredictable food supply early in life produced a significantly smaller repertoire of song phrases than those with a constant food supply. Social status during development was also significantly correlated with repertoire size, with dominant birds producing more phrase types. This study therefore provides novel evidence that social as well as nutritional history may be important in shaping the song signal in this species.