Resource choice behavior has enormous fitness consequences and can drive niche expansion. However, individual behavioral choices are often mediated by context, determined by past experience. Do such context-dependent behaviors reflect maladaptive variation or are they locally adaptive? Using Tribolium castaneum (the red flour beetle), we demonstrate that context-dependent oviposition behavior reflects distinct, context-specific local fitness peaks. We measured offspring fitness to generate fitness landscapes as a function of all possible oviposition behaviors (i.e., combinations of fecundity and resource preference) in a habitat containing optimal and suboptimal resource patches. We did this by experimentally manipulating egg allocation across patches, which allowed us to assess behaviors not typically observed in the laboratory. We found that females from different age and competition contexts exhibit distinct behaviors which optimize different fitness components, linked in a tradeoff. With prior exposure to strong competition and increasing age, females produce few but fast-developing offspring that are advantageous under high resource competition. In contrast, young naïve females produce significantly more (but slower developing) offspring, which is beneficial under weak competition. Systematically mapping complete context-dependent fitness landscapes is thus critical to infer behavioral optimality and offers predictive power in novel contexts.