Reciprocal adaptation between hosts and symbionts can drive the maintenance of symbioses, resulting in coevolution and beneficial genotypic interactions. Consequently, hosts may experience decreased fitness when paired with non-sympatric partners compared to sympatric symbionts. However, coevolution does not preclude conflict—host and symbiont can act to advance their own fitness interests, which do not necessarily align with those of their partner. Despite coevolution’s importance in extant symbioses, we know little about its role in shaping the origin of symbioses. Here, we tested the role of coevolution in establishing a novel association by experimentally (co)evolving a host with a protective bacterium under environmental stress. While evolution in the presence of non-evolving bacteria facilitated host adaptation, co-passaged hosts did not exhibit greater adaptation rates than hosts paired with non-evolving bacteria. Furthermore, co-passaged hosts exhibited greater fecundity when paired with sympatric, co-passaged bacteria compared to co-passaged bacteria with which they did not share an evolutionary history. Thus, shared evolutionary history between the hosts and microbes actually reduced host fitness and has the potential to impede evolution of new beneficial associations.