Many host-associated microbes are transmitted between individual hosts via the environment and, therefore, need to succeed both within a host and a connected environmental habitat. These microbes might invest differentially into the two habitats, potentially leading to fitness trade-offs and distinct life history strategies that ultimately shape the host-associated microbial communities. In this study, we investigated how the presence of distinct bacterial life history strategies affects microbiota characteristics along a host-associated life cycle, using the nematode host Caenorhabditis elegans and two naturally associated bacteria, Pseudomonas lurida and Ochrobactrum vermis, as an experimentally tractable model. Based on genomic life history prediction and experimental fitness characterizations, we identified distinct ecological strategies for the bacteria: whereas P. lurida dominated the free-living environment, O. vermis was more abundant in the host. Using mathematical modelling, experimental evolution, and whole genome sequencing, we next assessed whether the two distinct ecological strategies influence further adaptation to the host-associated life cycle. We found that (i) the host-specialist O. vermis did not further adapt to the two habitats, whereas (ii) the initially better environmental competitor P. lurida adapted to the life cycle, leading to its increased abundance in both environment and host. Evolutionary adaptation of P. lurida caused a shift in microbiota composition in the host, which in turn, resulted in a significant increase in host fitness. Overall, our results highlight the role of microbial life history strategies in shaping the characteristics and evolution of host-microbe interactions and suggest a potential selective advantage of better environmental competitors.