Many insects depend on obligate mutualistic bacteria to provide essential nutrients lacking from their diet. Most aphids, whose diet consists of phloem, rely on the bacterial endosymbiont Buchnera aphidicola to supply essential amino acids and B vitamins. However, in some aphid species, provision of these nutrients is partitioned between Buchnera and a younger bacterial partner, whose identity varies across aphid lineages. Little is known about the origin and the evolutionary stability of these di-symbiotic systems. It is also unclear whether the novel symbionts merely compensate for losses in Buchnera or carry new nutritional functions. Using whole-genome endosymbiont sequences of nine Cinara aphids that harbour an Erwinia-related symbiont to complement Buchnera, we show that the Erwinia association arose from a single event of symbiont lifestyle shift, from a free-living to an obligate intracellular one. This event resulted in drastic genome reduction, long-term genome stasis, and co-divergence with aphids. Fluorescence in situ hybridisation reveals that Erwinia inhabits its own bacteriocytes near Buchnera's. Altogether these results depict a scenario for the establishment of Erwinia as an obligate symbiont that mirrors Buchnera's. Additionally, we found that the Erwinia vitamin-biosynthetic genes not only compensate for Buchnera's deficiencies, but also provide a new nutritional function; whose genes have been horizontally acquired from a Sodalis-related bacterium. A subset of these genes have been subsequently transferred to a new Hamiltonella co-obligate symbiont in one specific Cinara lineage. These results show that the establishment and dynamics of multi-partner endosymbioses can be mediated by lateral gene transfers between co-ocurring symbionts.