Alfalfa, Medicago sativa L., is one of the most important forage legumes worldwide, but acid soils and associated aluminum toxicity dramatically decrease its productivity and persistence. Limited variability for Al tolerance is present within tetraploid germplasm, and no aluminum tolerant cultivar is commercially available. The tetraploid aluminum tolerant genotype Altet-4, derived from a source of tolerance identified in diploid M. sativa subsp. caerulea, was crossed to NECS-141, a semi-dormant breeding line, to produce a mapping population of 185 individuals. The population was evaluated in a modified soil-based greenhouse assay to assess individual genotype performance in unlimed, aluminum rich, acid soil compared with performance in limed soil without Al toxicity. Rooted stem cuttings were grown for 6 weeks in both types of soil and harvested. Root and shoot dry weight in both soil treatments, and the ratio of unlimed:limed of these traits were measured or calculated. Linkage maps were constructed using molecular markers, generating a composite map length of 840 cM and 749 cM for Altet4 and NECS-141, respectively. Single-factor analysis and interval mapping identified quantitative trait loci (QTL) on Altet-4 linkage groups 1, 2, 5, 6, and 7, and on NECS-141 linkage group 5. Phenotypic variation explained by individual QTL varied from 9.5 to 35.3%. Some of these QTLs were detected in multiple environments and for multiple traits, but others were environment-specific, suggesting that multiple mechanisms of Al tolerance exist. Introgression of these Al tolerance QTLs into elite breeding lines will lead to cultivars with enhanced Al tolerance.