Nitrogen is an important nutrient for plant growth and tuber quality of potato. Since potato crop requires high dose of N, improving nitrogen use efficiency (NUE) of plant is an inevitable approach to minimize N fertilization. The aim of this study was to identify and characterize microRNAs (miRNAs) by small RNA sequencing in potato plants grown in aeroponic under two contrasting N (high and low) regimes. A total of 119 conserved miRNAs belonging to 41 miRNAs families, and 1002 putative novel miRNAs were identified. From total, 52 and 54 conserved miRNAs, and 404 and 628 putative novel miRNAs were differentially expressed in roots and shoots, respectively under low N stress. Of total 34,135 predicted targets, the gene ontology (GO) analysis indicated that maximum targets belong to biological process followed by molecular function and cellular component. Eexpression levels of the selected miRNAs and targets were validated by real time-quantitative polymerase chain reaction (RT-qPCR) analysis. Two predicted targets of potential miRNAs (miR397 and miR398) were validated by 5' RLM-RACE (RNA ligase mediated rapid amplification of cDNA ends). In general, predicted targets are associated with stress-related, kinase, transporters and transcription factors such as universal stress protein, heat shock protein, salt-tolerance protein, calmodulin binding protein, serine-threonine protein kinsae, Cdk10/11- cyclin dependent kinase, amino acid transporter, nitrate transporter, sugar transporter, transcription factor, F-box family protein, and zinc finger protein etc. Our study highlights that miR397 and miR398 play crucial role in potato during low N stress management. Moreover, study provides insights to modulate miRNAs and their predicted targets to develop N-use efficient potato using transgenic/genome-editing tools in future.