We describe an association mapping approach using natural populations of perennial ryegrass (Lolium perenne L.) to identify molecular markers associated with heading date, an important trait affecting seasonal production, tillering, digestibility and grassland management regimes. Twenty-three natural populations originating from throughout Europe, with heading date phenotypes ranging from very early to very late, as well as three synthetic populations (varieties) were used for molecular marker genotyping using AFLP. In total, 589 polymorphic markers were identified. Hierarchical clustering, principal coordinate and other statistical analyses identified four outlying populations forming a clearly distinct sub-group. Removal of those four populations from the subsequent analysis reduced population sub-structure twofold. However, this made relatively little difference to the result of the association analysis. Linear regression identified three markers whose frequency of occurrence correlated with the heading date phenotype. Moreover, these markers were shown to be closely linked to each other within a major QTL on Chromosome 7, explaining 70% of the total variation in heading date. Pairwise linkage disequilibrium among them was also significant. These results suggest that association mapping approaches may be feasible in L. perenne, and that the use of natural populations could provide a useful source of genetic variation in traits of importance in crop improvement.