Approximately ten percent of insect species require maternally inherited intracellular bacteria to survive and reproduce, generally because these bacterial mutualists provide nutritional supplementation to an insect surviving on a limited substrate. These intracellular insect symbionts include bacteria with the smallest cellular genomes yet sequenced, which have an organelle-like structural stability and mutation rate, attributable to their small effective population sizes and host-limited lifestyles. Furthermore, some insects are reliant on more than one obligate heritable symbiont, and generally these multi-symbiont systems show a division of labor in terms of their nutrient production. A subset of mealybugs (Pseudococcidae) rely on a binary obligate symbiont set where one partner, a gammaproteobacterium, is embedded in the cytoplasm of the other, a betaproteobacterium: this is the only known extant intracellular mutualism between two bacteria, within or outside of an insect host. The genomes of both bacterial partners show immense reduction and complementarity in the insect host where they have been best studied, Planococcus citri; despite this tight interdependence, however, the gammaproteobacterial partner has been replaced repeatedly in the mealybug lineage by relatives of the widespread insect endosymbiont Sodalis. This series of subsititutions has provided us with a unique opportunity to enhance our understanding of the process by which free-living bacteria are biochemically and physiologically integrated into highly specialized, multi-partite symbioses.