Within-species colour variation is widespread among animals. Understanding how this arises can elucidate evolutionary mechanisms, such as those underlying reproductive isolation and speciation. Here, we investigated whether five island populations of Aegean wall lizards (Podarcis erhardii) have more effective camouflage against their own (local) island substrates than against other (non-local) island substrates to avian predators, and whether this was linked to island differences in substrate appearance. We also investigated whether degree of local substrate matching varied among island populations and between sexes. In most populations, both sexes were better matched against local backgrounds than against non-local backgrounds, particularly in terms of luminance (perceived lightness), which usually occurred when local and non-local backgrounds were different in appearance. This was found even between island populations that historically had a land connection and in populations that have been isolated relatively recently, suggesting that isolation in these distinct island environments has been sufficient to cause enhanced local background matching, sometimes on a rapid evolutionary time-scale. However, heightened local matching was poorer in populations inhabiting more variable and unstable environments with a prolonged history of volcanic activity. Overall, these results show that lizard coloration is tuned to provide camouflage in local environments, either due to genetic adaptation or changes during development. Yet, the occurrence and extent of selection for local matching may depend on specific conditions associated with local ecology and biogeographic history. These results emphasize how anti-predator adaptations to different environments can drive divergence within a species, which may contribute to reproductive isolation among populations and lead to ecological speciation.