Dispersal is a major determinant of the ecological and evolutionary dynamics of natural populations. Individuals differ greatly in the likelihood and distance of dispersal, but it is generally unclear to what extent intrinsic, possibly genetic, differences contribute. Here we present the first explicit empirical evidence for genetic coupling of local dispersal and exploratory behaviour, a key 'animal personality' trait. Using relatedness data from a multi-generation pedigree of free-living great tits (Parus major), we find quantitative genetic variation for both the distance of local dispersal within our study area and the rate at which individuals explore a novel environment. Moreover, we find a strongly positive genetic correlation between local dispersal distance and exploration rate, despite a weak and non-significant phenotypic correlation. These findings demonstrate a potentially important behavioural mechanism underlying heritable differences in local dispersal and highlight the potential for concerted evolution of dispersal and animal personality in response to selection.