Protective symbionts can allow hosts to occupy otherwise uninhabitable niches. Despite the importance of symbionts in host evolution, we know little about how these associations arise. Encountering a microbe that can improve host fitness in a stressful environment may favor persistent interactions with that microbe, potentially facilitating a long-term association. The bacterium Bacillus subtilis protects Caenorhabditis elegans nematodes from heat shock by increasing host fecundity compared to the non-protective Escherichia coli. In this study, we ask how the protection provided by the bacterium affects the host’s evolutionary trajectory. Because of the stark fitness contrast between hosts heat shocked on B. subtilis versus E. coli, we tested whether the protection conferred by the bacteria could increase the rate of host adaptation to a stressful environment. We passaged nematodes on B. subtilis or E. coli, under heat stress or standard conditions for 20 host generations of selection. When assayed under heat stress, we found that hosts exhibited the greatest fitness increase when evolved with B. subtilis under stress compared to when evolved with E. coli or under standard (non-stressful) conditions. Furthermore, despite not directly selecting for increased B. subtilis fitness, we found that hosts evolved to harbor more B. subtilis as they adapted to heat stress. Our findings demonstrate that the context under which hosts evolve is important for the evolution of beneficial associations and that protective microbes can facilitate host adaptation to stress. In turn, such host adaptation can benefit the microbe.