MicroRNAs (miRNAs) play important roles in response of plants to biotic and abiotic stresses. Aluminum (Al) toxicity is a major factor limiting plant growth in acidic soils. However, there has been limited report on the involvement of miRNAs in response of plants to toxic Al(3+). To identify Al(3+)-responsive miRNAs at whole-genome level, high-throughput sequencing technology was used to sequence libraries constructed from root apices of the model legume plant Medicago truncatula treated with and without Al(3+). High-throughput sequencing of the control and two Al(3+)-treated libraries led to generation of 17.1, 14.1 and 17.4 M primary reads, respectively. We identified 326 known miRNAs and 21 new miRNAs. Among the miRNAs, expression of 23 miRNAs was responsive to Al(3+), and the majority of Al(3+)-responsive mRNAs was down-regulated. We further classified the Al(3+)-responsive miRNAs into three groups based on their expression patterns: rapid-responsive, late-responsive and sustained-responsive miRNAs. The majority of Al(3+)-responsive miRNAs belonged to the 'rapid-responsive' category, i.e. they were responsive to short-term, but not long-term Al(3+) treatment. The Al(3+)-responsive miRNAs were also verified by quantitative real-time PCR. The potential targets of the 21 new miRNAs were predicted to be involved in diverse cellular processes in plants, and their potential roles in Al(3+)-induced inhibition of root growth were discussed. These findings provide valuable information for functional characterization of miRNAs in Al(3+) toxicity and tolerance.