Animals differ in their behaviour comparable to how humans differ in personality: individuals consistently differ in suites of correlated traits. Relationships between ‘personality traits’ and fitness imply that personality traits can evolve by means of natural selection. We studied whether animal personality is also involved in sexual selection. We investigated whether exploratory behaviour (an aspect of animal personality, ranging from ‘slow’ to ‘fast’) correlated with the occurrence of extrapair paternity (EPP) in broods of wild great tits. We expected that EPP rates should be highest for females mated with social partners of the same personality type (i.e. for slow–slow or fast–fast pairs, but not other pair combinations). We found that the likelihood of EPP was highest for these pairs. Disassortative extrapair mating with respect to personality can be the consequence of several non-mutually exclusive processes. It might be caused by adaptive mate choice, which allows assortatively paired females to produce offspring with either more variable or more intermediate phenotypes, but it could also be the consequence of behavioural incompatibility between extreme behavioural phenotypes. Our findings indicate that personality differences play a role in the mechanism behind extrapair behaviours and we therefore conclude that it is now plausible that partner preference is based not only on morphological characteristics, but also on consistent behavioural traits or personality.