Genome-Environment Associations (GEA) 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 (GWAS). 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 (Phaseolus vulgaris 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 SNP markers. Three indices of heat stress were developed for each accession and inputted in last generation algorithms (i.e. 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 1kb 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 (MED23, MED25, HSFB1, HSP40 and HSP20). We also found protein domains related to thermo stability in plants such as S1 and Zinc finger A20 & AN1. Other genes were related to biological processes that may correlate with plant tolerance to high temperature, such as time to flowering (MED25, MBD9 and PAP), germination and seedling development (Pkinase_Tyr, Ankyrin-B and Family Glicosil-hydrolase), cell wall stability (GAE6), and signaling pathway of abiotic stress via Abscisic Acid (Histone-like transcription factors NFYB and phospholipase C) and Auxin (Auxin response factor and AUX_IAA). 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.