Sorghum [Sorghum bicolor (L.) Moench] is important for smallholder production in semiarid parts of Uganda. Grain yields are low because of low soil fertility. Little fertilizer is used. Yield response to N, P, and K application, economically optimal rates for N, P, and K (EONR, EOPR, and EOKR, respectively), and N use efficiency (NUE) were evaluated at 11 site-seasons. Mean sorghum yield with no N applied (N0) was 0.69 Mg ha−1 and was consistently increased by a mean of 230% with N application. Mean EONRs were 34 to 18 kg ha−1 N with fertilizer use cost to grain price ratios (CPs) of 10 to 30, respectively. Mean EOPRs were 11 to 2 kg ha−1 P with CPs of 10 to 50, respectively. Sorghum did not respond to K application. Net economic returns were greater for N than P application. Mean aboveground biomass N with 0 and 90 kg ha−1 N applied was 31.3 and 75.9 kg ha−1, respectively. Grain N concentration, N harvest index, and internal NUE at the EONR were 1.67%, 53.2%, and 31.8 kg kg−1, respectively, and higher than for N0. Mean recovery efficiency, partial factor productivity, and agronomic efficiency declined with increased N rate and were 135%, 79 kg kg−1, and 52 kg kg−1, respectively, at the EONR. The profit potential of fertilizer N use is high for smallholder sorghum production in Uganda. Policy interventions to reduce fertilizer cost and improve grain marketing efficiency will enable smallholders to increase fertilizer use for substantial increases in sorghum production.