How and if organisms can adapt to changing temperatures has drastic consequences for the natural world. Thermal adaptation involves finding a match between temperatures permitting growth and the expected temperature distribution of the environment. However, if and how this match is achieved, and how tightly linked species change together, are poorly understood. Paramecium bursaria is a ciliate that has a tight physiological interaction with endosymbiotic green algae (zoochlorellae). We subjected a wild population of P. bursaria to a cold and warm climate (20℃ and 32℃) for ~300 generations. We then measured the thermal performance curve (TPC) for intrinsic rate of growth (r_max ) for these evolved lines across temperatures. We also evaluated number and size of the zoochlorellae populations within paramecia cells. TPCs for warm-adapted populations were shallower and broader than TPCs of cold-adapted populations, indicating that the warm populations adapted by moving along a thermal generalist/specialist trade off rather than right-shifting the TPC. Zoochlorellae populations within cold-adapted paramecia had fewer and larger zoochlorellae than hot-adapted paramecia, indicating phenotypic shifts in the endosymbiont accompany thermal adaptation in the host. Our results provide new and novel insight into how species involved in complex interactions will be affected by continuing increasing global temperatures.