A fundamental question in life-history evolution is how organisms cope with fluctuating environments, including variation between stressful and benign conditions. For short-lived organisms, environments commonly vary between generations. Using a novel experimental design, we exposed wild-derived Drosophila melanogaster to three different selection regimes: one where generations alternated between starvation and benign conditions, and starvation was always preceded by early exposure to cold; another where starvation and benign conditions alternated in the same way, but cold shock sometimes preceded starvation and sometimes benign conditions; and a third where conditions were always benign. Using six replicate populations per selection regime, we found that selected flies increased their starvation resistance, most strongly for the regime where cold and starvation were reliably combined, and this occurred without decreased fecundity or extended developmental time. The selected flies became stress resistant, displayed a pronounced increase in early-life food intake and resource storage. In contrast to previous experiments selecting for increased starvation resistance in D. melanogaster, we did not find increased storage of lipids as the main response, but instead that, in particular for females, storage of carbohydrates was more pronounced. We argue that faster mobilization of carbohydrates is advantageous in fluctuating environments and conclude that the phenotype that evolved in our experiment corresponds to a compromise between the requirements of stressful and benign environments.