Adaptation to local environmental conditions and the range dynamics of populations can influence evolutionary divergence along environmental gradients. Thus, it is important to investigate patterns of both phenotypic and genetic variation among populations to reveal the respective roles of these two types of factors in driving population differentiation. Here, we test for evidence of phenotypic and genetic structure across populations of a passerine bird (Zosterops borbonicus) distributed along a steep elevational gradient on the island of Réunion. Using eleven microsatellite loci screened in 401 individuals from 18 localities distributed along the gradient, we found that genetic differentiation occurred at two spatial levels: (i) between two main population groups corresponding to highland and lowland areas, respectively, and (ii) within each of these two groups. In contrast, several morphological traits varied gradually along the gradient. Comparison of neutral genetic differentiation (FST) and phenotypic differentiation (PST) showed that PST largely exceeds FST at several morphological traits, which is consistent with a role for local adaptation in driving morphological divergence along the gradient. Overall, our results revealed an area of secondary contact mid-way up the gradient between two major, cryptic, population groups likely diverged in allopatry. Remarkably, local adaptation has shaped phenotypic differentiation irrespective of population history, resulting in different patterns of variation along the elevational gradient. Our findings underscore the importance of understanding both historical and selective factors when trying to explain variation along environmental gradients.