Throughout the Western World huge numbers of people regularly supply food for wild birds. However, evidence of negative impacts of winter feeding on future reproduction has highlighted a need to improve understanding of the underlying mechanisms shaping avian responses to supplementary food. Here, we test the possibility that carry-over effects are mediated via their impact on the phenotypes of breeding birds, either by influencing the phenotypic structure of populations through changes in winter survival and/or by more direct effects on the condition of breeding birds. Using a landscape-scale three-year study of blue tits (Cyanistes caeruleus), we demonstrate the importance of nutritional composition of supplementary food in determining carry-over effect outcomes. We show that breeding populations which had access to vitamin E-rich foods during the previous winter were comprised of individuals with reduced feather carotenoid concentrations, indicative of lower pre-feeding phenotypic condition, compared to fat-fed and unfed populations. This suggests that supplementary feeding in winter can result in altered population phenotypic structure at the time of breeding, perhaps by enhancing survival and recruitment of lower quality individuals. However, supplementation of a fat-rich diet during winter was detrimental to the oxidative state of breeding birds, with these phenotypic differences ultimately found to impact upon reproductive success. Our findings demonstrate the complex nature by which supplementary feeding can influence wild bird populations.