Environmental gradients constrain physiological performance and thus species’ ranges, suggesting that species occurrence in diverse environments may be associated with local adaptation. Genome-environment association analyses (GEAA) have become central for studies of local adaptation, yet they are sensitive to the spatial orientation of historical range expansions relative to landscape gradients. To test whether potentially adaptive genotypes occur in varied climates in wide-ranged species, we implemented GEAA on the basis of genome-wide data from the anole lizards Anolis ortonii and A. punctatus, which expanded from Amazonia, presently dominated by warm and wet settings, into the cooler and less rainy Atlantic Forest. To examine whether local adaptation has been constrained by population structure and history, we estimated effective population sizes, divergence times, and gene flow under a coalescent framework. In both species, divergence between Amazonian and Atlantic Forest populations dates back to the mid-Pleistocene, with subsequent gene flow. We recovered eleven candidate genes involved with metabolism, immunity, development, and cell signaling in A. punctatus, and found no loci whose frequency is associated with environmental gradients in A. ortonii. Distinct signatures of adaptation between these species are not associated with historical constraints or distinct climatic space occupancies. Similar patterns of spatial structure between selected and neutral SNPs along the climatic gradient, as supported by patterns of genetic clustering in A. punctatus, may have led to conservative GEAA performance. This study illustrates how tests of local adaptation can benefit from knowledge about species histories to support hypothesis formulation, sampling design, and landscape gradient characterization.