The importance of zinc (Zn) as a micronutrient essential for plant growth and development is becoming increasingly apparent. Much of the world's soil is Zn-deficient, and soil-based Zn deficiency is often accompanied by Zn deficiency in human populations. MicroRNAs (miRNAs) play important roles in the regulation of plant gene expression at the level of translation. Many miRNAs involved in the modulation of heavy metal toxicity responses in plants have been identified; however, the role of miRNAs in the plant Zn deficiency response is almost completely unknown. Using high-throughput Solexa sequencing, we identified several miRNAs that respond to Zn deficiency in Brassica juncea roots. At least 21 conserved candidate miRNA families, and 101 individual members within those families, were identified in both the control and the Zn-deficient B. juncea roots. Among this, 15 miRNAs from 9 miRNA families were differentially expressed in the control and Zn-deficient plants. Of the 15 differentially expressed miRNAs, 13 were up-regulated in the Zn-deficient B. juncea roots, and only two, miR399b and miR845a, were down-regulated. Bioinformatics analysis indicated that these miRNAs were involved in modulating phytohormone response, plant growth and development, and abiotic stress responses in B. juncea roots. These data help to lay the foundation for further understanding of miRNA function in the regulation of the plant Zn deficiency response and its impact on plant growth and development.