Elucidating the molecular basis of adaptive phenotypic variation represents a central aim in evolutionary biology. Traits exhibiting patterns of clinal variation represent excellent models for studies of molecular adaptation, especially when variation in phenotype can be linked to organismal fitness in different environments. Natural accessions of the model plant species Arabidopsis thaliana exhibit clinal variation in freezing tolerance that follows a gradient of temperature variability across the species’ native range (Zhen Y, Ungerer MC. 2008. Clinal variation in freezing tolerance among natural accessions of A. thaliana. New Phytol. 177:419–427). Here, we report that this pattern of variation is attributable, at least in part, to relaxed purifying selection on members of a small family of transcriptional activators (the CBF/DREB1s) in the species’ southern range. These regulatory genes play a critical role in the ability of A. thaliana plants to undergo cold acclimation and thereby achieve maximum freezing tolerance. Relative to accessions from northern regions, accessions of A. thaliana from the southern part of their geographic range exhibit levels of nonsynonymous nucleotide polymorphism that are approximately 2.8-fold higher across this small gene subfamily. Relaxed selection on the CBF/DREB1s in southern accessions also has resulted in multiple mutations in regulatory regions resulting in abrogated expression of particular subfamily members in particular accessions. These coding-region and regulatory mutations compromise the ability of these genes to act as efficient transcriptional activators during the cold acclimation process, as determined by reductions in rates of induction and maximum levels of expression in the downstream genes they regulate. This study highlights the potential role of regulatory genes in underlying adaptive phenotypic variation in nature.