Exploring the natural genetic variability and its exploitation for improved Nitrogen Use Efficiency (NUE) in sorghum is one of the primary goals in the modern crop improvement programs. The integrated strategies include high-throughput phenotyping, next generation sequencing (NGS)-based genotyping technologies, and a priori selected candidate gene studies that help understand the detailed physiological and molecular mechanisms underpinning this complex trait. A set of sixty diverse sorghum genotypes was evaluated for different vegetative, reproductive, and yield traits related to NUE in the field (under three N regimes) for two seasons. Significant variations for different yield and related traits under 0 and 50% N confirmed the availability of native genetic variability in sorghum under low N regimes. Sorghum genotypes with distinct genetic background had interestingly similar NUE associated traits. The Genotyping-By-Sequencing based SNPs (>89 K) were used to study the population structure, and phylogenetic groupings identified three distinct groups. The information of grain N and stalk N content of the individuals covered on the phylogenetic groups indicated randomness in the distribution for adaptation under variable N regimes. This study identified promising sorghum genotypes with consistent performance under varying environments, with buffer capacity for yield under low N conditions. We also report better performing genotypes for varied production use-grain, stover, and dual-purpose sorghum having differential adaptation response to NUE traits. Expression profiling of NUE associated genes in shoot and root tissues of contrasting lines (PVK801 and HDW703) grown in varying N conditions revealed interesting outcomes. Root tissues of contrasting lines exhibited differential expression profiles for transporter genes [ammonium transporter (SbAMT), nitrate transporters (SbNRT)]; primary assimilatory (glutamine synthetase (SbGS), glutamate synthase (SbGOGAT[NADH], SbGOGAT[Fd]), assimilatory genes [nitrite reductase (SbNiR[NADH]3)]; and amino acid biosynthesis associated gene [glutamate dehydrogenase (SbGDH)]. Identification and expression profiling of contrasting sorghum genotypes in varying N dosages will provide new information to understand the response of NUE genes toward adaptation to the differential N regimes in sorghum. High NUE genotypes identified from this study could be potential candidates for in-depth molecular analysis and contribute toward the development of N efficient sorghum cultivars.