Periods of nutrient shortage impose strong selection on animal populations. Experimental studies of genetic adaptation to nutrient shortage largely focus on resistance to acute starvation at adult stage; it is not clear how conclusions drawn from these studies extrapolate to other forms of nutritional stress. We studied the genomic signature of adaptation to chronic juvenile malnutrition in six populations of Drosophila melanogaster evolved for 150 generations on an extremely nutrient-poor larval diet. Comparison with control populations evolved on standard food revealed repeatable genomic differentiation between the two set of population, involving >3,000 candidate SNPs forming >100 independently evolving clusters. The candidate genomic regions were enriched in genes implicated in hormone, carbohydrate, and lipid metabolism, including some with known effects on fitness-related life-history traits. Rather than being close to fixation, a substantial fraction of candidate SNPs segregated at intermediate allele frequencies in all malnutrition-adapted populations. This, together with patterns of among-population variation in allele frequencies and estimates of Tajima's D, suggests that the poor diet results in balancing selection on some genomic regions. Our candidate genes for tolerance to larval malnutrition showed a high overlap with genes previously implicated in acute starvation resistance. However, adaptation to larval malnutrition in our study was associated with reduced tolerance to acute adult starvation. Thus, rather than reflecting synergy, the shared genomic architecture appears to mediate an evolutionary trade-off between tolerances to these two forms of nutritional stress.