The complex interrelationships among individuals within social environments can exert selection pressures on social skills: those behaviours and cognitive processes that allow animals to manipulate and out-reproduce others. Social complexity can also have a developmental effect on social skills by providing individuals with opportunities to hone their skills by dealing with the challenges posed in within-group interactions. We examined how social skills develop in captive, adult male brown-headed cowbirds (Molothrus ater) that were exposed to differing levels of 'social complexity' across a 2-year experiment. After each year, subjects housed in groups with dynamic social structure (where many individuals entered and exited the groups during the year) outcompeted birds who had been housed in static groups. Exposure to dynamic structure subsequently led to substantial changes to the social networks of the home conditions during the breeding season. Static groups were characterized by a predictable relationship between singing and reproductive success that was stable across years. In dynamic conditions, however, males showed significant variability in their dominance status, their courting and even in their mating success. Reproductive success of males varied dramatically across years and was responsive to social learning in adulthood, and socially dynamic environments 'trained' individuals to be better competitors, even at an age when the development of many traits important for breeding (like song quality) had ended.