Social environments have an important effect on a range of ecological processes, and form a crucial component of selection. However, little is known of the link between personality, social behaviour and population structure. We combine a well-understood personality trait with large-scale social networks in wild songbirds, and show that personality underpins multiple aspects of social organisation. First, we demonstrate a relationship between network centrality and personality with 'proactive' (fast-exploring) individuals associating weakly with greater numbers of conspecifics and moving between flocks. Second, temporal stability of associations relates to personality: 'reactive' (slow-exploring) birds form synergistically stable relationships. Finally, we show that personality influences social structure, with males non-randomly distributed across groups. These results provide strong evidence that songbirds follow alternative social strategies related to personality. This has implications not only for the causes of social network structure but also for the strength and direction of selection on personality in natural populations.