Climate can exert an effect on the strength of sexual selection, but empirical evidence is limited. Here, we tested if climate predicts the geographic distribution and introgressive spread of sexually selected male colour ornamentation across 114 populations of the common wall lizard, Podarcis muralis. Colouration was highly structured across the landscape, and did not reflect genetic differentiation. Instead, colour ornamentation was consistently exaggerated in hot and dry environments, suggesting that climate-driven selection maintains geographic variation in spite of gene flow. Introgression of colour ornamentation into a distantly related lineage appears to be ongoing and was particularly pronounced in warm climates with wet winters and dry summers. Combined, these results suggest that sexual ornamentation is consistently favoured in climates that allow a prolonged reproductive season and high and reliable opportunities for lizard activity. This pattern corroborates theoretical predictions that such climatic conditions reduce the temporal clustering of receptive females and increase male-male competition, resulting in strong sexual selection. In summary, we provide compelling evidence for the importance of climate for the evolution of colour ornamentation, and demonstrate that geographic variation in the strength of sexual selection influences introgression of this phenotype.