The aim of this study was to reveal mechanisms responsible for nitrogen (N) stress in two contrasting Populus clones. Leaves of Nanlin 1388 (N stress-insensitive clone hybrids of Populus deltoides Bart.CV. × Populus euramericana (Dode) Guineir CV) and Nanlin 895 (N stress-sensitive clone hybrids of Populus deltoides Bart.CV. × Populus euramericana (Dode) Guineir CV) were harvested and analyzed. Different responses visible in photosynthesis, N and carbon contents, physiological traits, and chlorophyll were observed. The Solexa/Illumina’s digital gene expression system was used to investigate differentially expressed miRNAs and mRNAs under N stress. Target profiling, and biological network and function analyses were also performed. Randomly selected mRNAs and miRNAs were validated by quantitative reverse transcription polymerase chain reaction. In all, 110 Nanlin 1388 and 122 Nanlin 895 miRNAs were differentially expressed, among which 34 and 23 miRNAs were newly found in the two clones, respectively. Under N stress, a total of 329 and 98 mRNAs were regulated in N stress-insensitive and -sensitive clones, respectively. Notably, the miR396 family and its regulated mRNAs were altered in both clones under N stress, while miR646 was regulated only in the N stress-insensitive clone (Nanlin 1388), and miR156, miR319 and miR393 in the N stress-sensitive clone (Nanlin 895). Gene ontology and Kyoto Encyclopedia of Genes and Genomes analyses also proved several clone-specific functions and pathways. These findings may be significant for understanding the genetic responses of Populus to N stress.