Genome–environment associations (GEA) in crop wild relatives that exhibit natural adaptation enable the identification of adaptive loci, which may be important in crop breeding for abiotic stress tolerance. Leafless Vanilla species in Madagascar have developed such adaptation and their speciation was shown to involve ecological selection by bioclimatic factors. In this study, the feasibility of a GEA approach was assessed using accessions of V. perrieri and V. bosseri, which are widely distributed in Madagascar. Genetic differentiation has been observed across diverse habitat types, using data from seven microsatellites. Principal component analyses of 19 environmental variables revealed a bioclimatic structure based on sample collection sites. For each species, redundancy analyses demonstrated that geographic distance (Isolation By Distance) and environmental variations (Isolation By Environment) (temperatures and precipitations) contributed to the genetic structure of the populations. These results indicate the presence of local adaptation in populations of these two species and suggest that they represent appropriate model species for studying the climatic adaptation of vanilla plants. Therefore, Genotyping-By-Sequencing (GBS) markers were developed for V. perrieri to identify candidate markers through a preliminary GEA analysis. Ultimately, the candidate loci identified will be useful for the selection of heat and drought-tolerant vanilla cultivars.