Aluminum (Al) toxicity in acid soils is a major limitation to the production of alfalfa (Medicago sativa subsp. sativa L.) in the USA. Developing Al-tolerant alfalfa cultivars is one approach to overcome this constraint. Accessions of wild diploid alfalfa (M. sativa subsp. coerulea) have been found to be a source of useful genes for Al tolerance. Previously, two genomic regions associated with Al tolerance were identified in this diploid species using restriction fragment length polymorphism (RFLP) markers and single marker analysis. This study was conducted to identify additional Al-tolerance quantitative trait loci (QTLs); to identify simple sequence repeat (SSR) markers that flank the previously identified QTLs; to map candidate genes associated with Al tolerance from other plant species; and to test for co-localization with mapped QTLs. A genetic linkage map was constructed using EST-SSR markers in a population of 130 BC1F1 plants derived from the cross between Al-sensitive and Al-tolerant genotypes. Three putative QTLs on linkage groups LG I, LG II and LG III, explaining 38, 16 and 27% of the phenotypic variation, respectively, were identified. Six candidate gene markers designed from Medicago truncatula ESTs that showed homology to known Al-tolerance genes identified in other plant species were placed on the QTL map. A marker designed from a candidate gene involved in malic acid release mapped near a marginally significant QTL (LOD 2.83) on LG I. The SSR markers flanking these QTLs will be useful for transferring them to cultivated alfalfa via marker-assisted selection and for pyramiding Al tolerance QTLs.