Durum wheat highly depends on nitrogen for seed development and yield, and the obtainment of varieties with a better nitrogen use efficiency is crucial to reduce production costs and environmental pollution. In this study, sequencing of two small RNA libraries obtained from tissues of Ciccio and Svevo cultivars grown under nitrogen starvation conditions produced 84 novel, and 161 conserved miRNAs. Of these, 7 novel and 13 known miRNAs were newly identified in this work. Quantitative PCR analysis of selected miRNAs highlighted that the expression levels of some of them depends on the tissue and on the cultivar, Svevo being the most responsive to nitrogen starvation. A number of target genes were predicted to be involved in nitrogen metabolism. An inverse correlation for the qPCR expression data of miRNA/target pairs miR399b/PHO2, miR393c/AFB2, ttu-novel-61/CCAAT-TF was observed in specific tissues or cultivar. Especially, ttu-novel-61 was down-regulated and its target CCAAT-TF up-regulated in almost all tissues both in Svevo and in Ciccio. Moreover, CCAAT-TF was confirmed to be cleaved by ttu-novel-61 at the expected site. The discovery of miRNAs involved in the response to nitrogen stress represents an important step towards functional analyses, with the final aim to design strategies for improving nitrogen use efficiency in durum wheat.