Nitrogen (N) is an important nutrient for plant growth. However, its excess application leads to environmental damage. Hence, improving nitrogen use efficiency (NUE) of plant is one of the plausible options to solve the problems. Aim of this study was to identify candidate genes involved in enhancing NUE in potato cv. Kufri Gaurav (N efficient). Plants were grown in aeroponic with two contrasting N regimes (low N: 0.75 mM, and high N: 7.5 mM). Higher NUE in Kufri Gaurav was observed in low N based on the parameters like NUE, NUpE (N uptake efficiency), NUtE (N utilization efficiency) and AgNUE (agronomic NUE). Further, global gene expression profiles in root, leaf and stolon tissues were analyzed by RNA-sequencing using Ion Proton™ System. Quality data (≥Q20) of 2.04–2.73 Gb per sample were mapped with the potato genome. Statistically significant (P ≤ 0.05) differentially expressed genes (DEGs) were identified such as 176 (up-regulated) and 30 (down-regulated) in leaves, 39 (up-regulated) and 105 (down-regulated) in roots, and 81 (up-regulated) and 694 (down-regulated) in stolons. The gene ontology (GO) terms like metabolic process, cellular process and catalytic activity were predominant. Our RT-qPCR analysis confirmed the gene expression profiles of RNA-seq. Overall, we identified candidate genes associated with improving NUE such as superoxide dismutase, GDSL esterase lipase, probable phosphatase 2C, high affinity nitrate transporters, sugar transporter, proline rich proteins, transcription factors (VQ motif, SPX domain, bHLH) etc. Our findings suggest that these candidate genes probably play crucial roles in enhancing NUE in potato.