Although several metallic elements are required for plant growth, excessive amounts of aluminum ions (Al3+) can result in the inhibition of root growth, thus triggering water and nutrient deficiencies. Plants under stress undergo gene expression changes in specific genes or post-transcriptional gene regulators, such as miRNAs, that can lead to stress tolerance. In this study, we investigated the miRNAs involved in the response of sugarcane to aluminum stress. Four miRNA libraries were generated using sugarcane roots of one tolerant and one sensitive sugarcane cultivar grown under aluminum stress and used to identify the miRNAs involved in the sugarcane aluminum toxicity response. The contrast in field phenotypes of sugarcane cultivars in the field during aluminum stress was reflected in the micro-transcriptome expression profiles. We identified 394 differentially expressed miRNAs in both cultivars, 104 of which were tolerant cultivar-specific, 116 were sensitive cultivar-specific, and 87 of which were common among cultivars. In addition, 52% of differentially expressed miRNAs were upregulated in the tolerant cultivar while the majority of differentially expressed miRNAs in the sensitive cultivar were downregulated. Real-time quantitative polymerase chain reaction was used to validate the expression levels of differentially expressed miRNAs. We also attempted to identify target genes of miRNAs of interest. Our results show that selected differentially expressed miRNAs of aluminum-stressed sugarcane cultivars play roles in signaling, root development, and lateral root formation. These genes thus may be important for aluminum tolerance in sugarcane and could be used in breeding programs to develop tolerant cultivars.