Mated pair bonds are integral to many animal societies, yet how individual variation in behaviour influences their formation remains largely unknown. In a population of wild great tits (Parus major), we show that personality shapes pair bonding: proactive males formed stronger pre-breeding pair bonds by meeting their future partners sooner and increasing their relationship strength at a faster rate. As a result, proactive males sampled fewer potential mates. Thus, personality may have important implications for social relationship dynamics and emergent social structure.