Genome-environment associations (GEAs) are a powerful strategy for the study of adaptive traits in wild plant populations, yet they still lack behind in the use of modern statistical methods as the ones suggested for genome-wide association studies (GWASs). In order to bridge this gap, we couple GEA with last-generation GWAS algorithms in common bean to identify novel sources of heat tolerance across naturally heterogeneous ecosystems. Common bean ( L.) is the most important legume for human consumption, and breeding it for resistance to heat stress is key because annual increases in atmospheric temperature are causing decreases in yield of up to 9% for every 1°C. A total of 78 geo-referenced wild accessions, spanning the two gene pools of common bean, were genotyped by sequencing (GBS), leading to the discovery of 23,373 single-nucleotide polymorphism (SNP) markers. Three indices of heat stress were developed for each accession and inputted in last-generation algorithms ( SUPER, FarmCPU, and BLINK) to identify putative associated loci with the environmental heterogeneity in heat stress. Best-fit models revealed 120 significantly associated alleles distributed in all 11 common bean chromosomes. Flanking candidate genes were identified using 1-kb genomic windows centered in each associated SNP marker. Some of these genes were directly linked to heat-responsive pathways, such as the activation of heat shock proteins (, , , , and ). We also found protein domains related to thermostability in plants such as and and . Other genes were related to biological processes that may correlate with plant tolerance to high temperature, such as time to flowering (, , and ), germination and seedling development (, , and ), cell wall stability (), and signaling pathway of abiotic stress via abscisic acid (histone-like transcription factors and ) and auxin ( and ). This work offers putative associated loci for marker-assisted and genomic selection for heat tolerance in common bean. It also demonstrates that it is feasible to identify genome-wide environmental associations with modest sample sizes by using a combination of various carefully chosen environmental indices and last-generation GWAS algorithms.