The large amounts of nitrogen (N) fertiliser applied to most cropping systems support high yields but cause N pollution. More efficient use of N in cropping systems can be achieved through improved N management practices combined with genetic improvement of the crop. The magnitude of genetic variation in sugarcane (Saccharum officinarum L.) for internal nitrogen use efficiency (iNUE, biomass produced per unit tissue N) was investigated as this could provide a basis for breeding varieties with reduced N demand. Genotypes of a mapping population were examined for biomass production and physiological variables under low or high N supply in controlled conditions. Key findings were: (i) genotypic variation for biomass production and iNUE was up to 3-fold greater under low than high N supply, (ii) elite parent Q165 was among the best performing genotypes for biomass and iNUE at high N but not at low N supply, and (iii) several genotypes had high iNUE at both N supplies. While glutamine synthetase (GS; EC 6.3.1.2) activity has been linked with grain yield in other crops, no direct relationship was observed between whole tissue GS activity and vegetative biomass or iNUE in sugarcane genotypes. Soluble protein content was negatively correlated with iNUE and biomass production. This study demonstrates that there is considerable genetic variation for iNUE in sugarcane, which can be exploited for breeding. It is proposed that breeding programs should assess genotypes not only at high N, but also at low N supply rates to select genotypes that produce high biomass with low and high N supply.