Early life adversity has known impacts on adult health and behavior, yet little is known about the gene-environment interactions (GEIs) that underlie these consequences. We used the fruit fly Drosophila melanogaster to show that chronic early nutritional adversity interacts with rover and sitter allelic variants of foraging (for) to affect adult exploratory behavior, a phenotype that is critical for foraging, and reproductive fitness. Chronic nutritional adversity during adulthood did not affect rover or sitter adult exploratory behavior; however, early nutritional adversity in the larval period increased sitter but not rover adult exploratory behavior. Increasing for gene expression in the mushroom bodies, an important center of integration in the fly brain, changed the amount of exploratory behavior exhibited by sitter adults when they did not experience early nutritional adversity but had no effect in sitters that experienced early nutritional adversity. Manipulation of the larval nutritional environment also affected adult reproductive output of sitters but not rovers, indicating GEIs on fitness itself. The natural for variants are an excellent model to examine how GEIs underlie the biological embedding of early experience.