Worldwide, nitrogen (N) is one of the most important and limiting factors of crop production. It is understood that increasing N rates decreases nitrogen use efficiency (NUE) in crops, especially in indeterminate crops like cotton. Therefore, to elucidate the molecular regulatory mechanism essential for improving NUE in cotton, we used Illumina RNA-Seq to understand the genotypic variation in the transcriptomic profile of cotton genotypes, CCRI-69 (N-efficient) and XLZ-30 (N-inefficient), in response to N starvation and resupply. The responses of both cotton genotypes varied dramatically at the transcriptional level. The results revealed that genetic differences exist between CCRI-69 and XLZ-30, including nutrient transporters, photosynthetic pathways, antioxidants, transcription factors (TF), and hormone signaling-related genes. WRKY in roots and AP2/ERF in shoots were the most differentially expressed TFs in both cotton genotypes, followed by AP2/ERF and MYB, respectively. Numerous genes involved in phytohormones, N transporters, antioxidant stress, and photosynthetic pathways were upregulated in both roots and shoots of CCRI-69, which showed that CCRI-69 had a greater ability of N absorption and use efficiency than XLZ-30. Thus, we deduced that high expression of N transporters and high biomass production through photosynthesis could be attributed to the high N efficiency in CCRI-69. In addition, hormone signaling pathways and high antioxidant activities may also contribute to the genotypic difference between cotton genotypes differing in NUE. Moreover, the hub genes identified in the co-expression analysis may provide new insights into the underlying molecular mechanisms involved in the high N-efficiency in CCRI-69 and could be used for further breeding of N-efficient cotton genotypes.