The intensive application of inorganic nitrogen underlies marked increases in crop production, but imposes detrimental effects on ecosystems: it is therefore crucial for future sustainable agriculture to improve the nitrogen-use efficiency of crop plants. Here we report the genetic basis of nitrogen-use efficiency associated with adaptation to local soils in rice (Oryza sativa L.). Using a panel of diverse rice germplasm collected from different ecogeographical regions, we performed a genome-wide association study on the tillering response to nitrogen—the trait that is most closely correlated with nitrogen-use efficiency in rice—and identified OsTCP19 as a modulator of this tillering response through its transcriptional response to nitrogen and its targeting to the tiller-promoting gene DWARF AND LOW-TILLERING (DLT). A 29-bp insertion and/or deletion in the OsTCP19 promoter confers a differential transcriptional response and variation in the tillering response to nitrogen among rice varieties. The allele of OsTCP19 associated with a high tillering response to nitrogen is prevalent in wild rice populations, but has largely been lost in modern cultivars: this loss correlates with increased local soil nitrogen content, which suggests that it might have contributed to geographical adaptation in rice. Introgression of the allele associated with a high tillering response into modern rice cultivars boosts grain yield and nitrogen-use efficiency under low or moderate levels of nitrogen, which demonstrates substantial potential for rice breeding and the amelioration of negative environment effects by reducing the application of nitrogen to crops.