Toxic levels of aluminum (Al) in acid soils inhibit root growth and cause substantial reduction in yields of Al-sensitive crops. Aluminum-tolerant cultivars detoxify Al through multiple mechanisms that are currently not well understood at genetic and molecular levels. To enhance our understanding of the molecular mechanisms involved in soybean Al tolerance and toxicity, we conducted proteomic analysis of soybean roots under Al stress using a tandem combination of 2-D-DIGE, mass spectrometry, and bioinformatics tools and Al-tolerant (PI 416937) and Al-sensitive (Young) soybean genotypes at 6, 51 or 72 h of Al treatment. Comparison of the protein profile changes revealed that aluminum induced Al tolerance related proteins and enzymes in Al-tolerant PI 416937 but evoked proteins related to general stress response in Al-sensitive Young. Specifically, Al upregulated: malate dehydrogenase, enolase, malate oxidoreductase, and pyruvate dehydrogenase, in PI 416937 but not in Young. These enzymes contribute to increased synthesis of citrate, a key organic acid involved in Al detoxification. We postulate that simultaneous transgenic overexpression of several of these enzymes would be a robust genetic engineering strategy for developing Al-tolerant crops.