Global change is forcing many species to shift their ranges. Colonizing new areas often requires adaptation to novel environmental conditions. Without adaptation, a colonizing population may only be temporarily sustained, thanks to migration. However, although immigrants are poorly adapted to the new habitat, they provide a source of genetic variation that might help the population to adapt to local conditions and persist. Theoretical models have been used to explore this “adaptive colonization” process, but without accounting for the role of symbionts, not withstanding the fact that practically all plant and animal species host symbionts on or inside their bodies. When colonizing new areas, host species also introduce their symbionts. Symbionts range from beneficial mutualists through simple passengers to harmful parasites, so some may help and some may hinder colonization. Furthermore, colonizing symbionts may also experience new selective pressures that would be likely to influence the colonization process. Here we bring together two fields in evolutionary biology—colonization of novel habitats and host–symbiont interactions—to address an important issue for understanding the response of populations to global change: How does the interaction between a colonizing host population and its co-introduced symbionts influence their respective abilities to adapt to new conditions? To do this, we developed a simulation that follows the eco-evolutionary dynamics of a host and its symbiont after being introduced into an empty island with external environmental conditions that differ from those in their source habitats. We considered different types of impact of the symbiont on the host, from strongly negative to strongly positive. Our results show that sometimes neither of the species can establish a population on the island, sometimes both do, and sometimes only the host succeeds. The outcome depends on the dispersal rates of both partners, on the interaction type and strength, and on their need for local adaptation.