Heterotrophic bacteria exploit diverse microhabitats in the ocean, from particles to transient gradients. Yet the degree to which genes and pathways can contribute to an organism’s fitness on such complex and variable natural resource landscapes remains poorly understood. Here, we determine the gene-by-gene fitness of a generalist saprophytic marine bacterium (Vibrio sp. F13 9CS106) on complex resources derived from its natural habitats - copepods (Apocyclops royi) and brown algae (Fucus vesiculosus) - and as reference substrates, glucose and the polysaccharide alginate, derived from brown algal cell walls. We find that resource complexity strongly buffers fitness costs of mutations, and that anabolic rather than catabolic pathways are more stringently required, likely due to functional redundancy in the latter. Moreover, while carbohydrate-rich algae requires several synthesis pathways, protein-rich Apocyclops does not, suggesting this ancestral habitat for Vibrios is a replete medium with metabolically redundant substrates. We also identify a candidate fitness trade-off for algal colonization: deletion of mshA increases mutant fitness. Our results demonstrate that gene fitness depends on habitat composition, and suggest that this generalist uses distinct resources in different natural habitats. The results further indicate that substrate replete conditions may lead to relatively relaxed selection on catabolic genes.