MicroRNAs (miRNAs) play important roles inresponse 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 Al3+. To identify Al3+-responsive miRNAs at wholegenome 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 Al3+. High-throughput sequencing of the control and two Al3+-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 Al3+, and the majority of Al3+-responsive mRNAs was down-regulated. We further classified the Al3+-responsive miRNAs into three groups based on their expression patterns: rapid-responsive, late-responsive and sustained-responsive miRNAs. The majority of Al3+- responsive miRNAs belonged to the ‘rapid-responsive’ category, i.e. they were responsive to short-term, but not long-term Al3+ treatment. The Al3+-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 Al3+-induced inhibition of root growth were discussed. These findings provide valuable information for functional characterization of miRNAs in Al3+ toxicity and tolerance.