The gut microbiota affects a wide spectrum of host physiological traits, including development [ 1–5 ], germline [ 6 ], immunity [ 7–9 ], nutrition [ 4, 10, 11 ], and longevity [ 12, 13 ]. Association with microbes also influences fitness-related behaviors such as mating [ 14 ] and social interactions [ 15, 16 ]. Although the gut microbiota is evidently important for host wellbeing, how hosts become associated with particular assemblages of microbes from the environment remains unclear. Here, we present evidence that the gut microbiota can modify microbial and nutritional preferences of Drosophila melanogaster. By experimentally manipulating the gut microbiota of flies subjected to behavioral and chemosensory assays, we found that fly-microbe attractions are shaped by the identity of the host microbiota. Conventional flies exhibit preference for their associated Lactobacillus, a behavior also present in axenic flies as adults and marginally as larvae. By contrast, fly preference for Acetobacter is primed by early-life exposure and can override the innate preference. These microbial preferences are largely olfactory guided and have profound impact on host foraging, as flies continuously trade off between acquiring beneficial microbes and balancing nutrients from food. Our study shows a role of animal microbiota in shaping host fitness-related behavior through their chemosensory responses, opening a research theme on the interrelationships between the microbiota, host sensory perception, and behavior.