Decreasing freshwater supply has led to the consideration of treated wastewater as an alternative source for agricultural irrigation. However, the higher content of heavy metals restricts their use in agricultural purposes. In the current study, a set of 181 SSR markers were used to perform association mapping in a structured sorghum population consisting of 107 accessions evaluated under tap-water and heavy-metals-containing water irrigation conditions. Significant differences between optimal and stressed growing conditions were shown in all evaluated phenotypic traits. Association mapping revealed 14 significant associations between 12 SSR markers and heavy metals stress indices of phenotypic traits (R2 = 11.54–30.85%). BLASTP annotation of QTLs genomic sequences identified 102 gene homologs, of which 19 are known to be implicated in phytoremediation and heavy metals tolerance. All nineteen genes exhibit differential expression patterns in heavy metals tolerant and susceptible sorghum accessions, and their transcriptional levels were highly elevated under heavy metals stress, indicating a possible functional association among these genes and provides strong evidence for their role in phytoremediation and heavy metal stress tolerance. Clustering and expression patterns of pentatricopeptide repeat and zinc finger protein genes suggest crucial roles of those genes in phytoremediation and heavy metals tolerance.