Maternally inherited symbionts are common in arthropods and many have important roles in host adaptation. The observation that specific symbiont lineages infect distantly related host species implies new interactions are commonly established by lateral transfer events. However, studies have shown that symbionts often perform poorly in novel hosts. We hypothesized selection on the symbiont may be sufficiently rapid that poor performance in a novel host environment is rapidly ameliorated, permitting symbiont maintenance. Here, we test this prediction for a Spiroplasma strain transinfected into the novel host Drosophila melanogaster. In the generations immediately following transinfection, the symbiont had low transmission efficiency to offspring and imposed severe fitness costs on its host. We observed that effects on host fitness evolved rapidly, being undetectable after 17 generations in the novel host, whereas vertical transmission efficiency was poorly responsive over this period. Our results suggest that long-term symbiosis may more readily be established in cases where symbionts perform poorly in just one aspect of symbiosis.