We aimed at mining the determinants of local adaptation in the two closest maize wild relatives, the teosintes Zea mays ssp parviglumis and ssp. mexicana. We sequenced 20 individuals from two lowland and two highland populations sampled along two altitudinal gradients, considered as biological replicates. Sequencing of two middle elevation parviglumis and mexicana populations in one gradient helped controlling for subspecies differentiation. We sequenced 20 individuals from the 6 populations and detected 8,479,581 SNPs. Population differentiation was greater between subspecies than within subspecies. We combined differentiation- and diversity-based methods to detect outlier SNPs that were further tested for correlation of allele frequencies with environmental variables. Outliers defined 43 candidate regions. We modified a haplotype-based method to incorporate genotype uncertainties in haplotype calling. We found haplotype signal consistency in 58% of our candidate regions along with several instances of the same haplotype being selected in lowland or highland populations. We found frequent co-localization between our candidate regions and loci involved in the variation of traits linked to plant-soil interactions indicating that soil is an important factor driving local adaptation in teosintes.