Many insects rely on bacterial symbionts with tiny genomes specialized for 
provisioning nutrients lacking in host diets. Xylem sap and phloem sap are both 
deficient as insect diets, but differ dramatically in nutrient content, 
potentially affecting symbiont genome evolution. For sap-feeding insects, 
sequenced symbiont genomes are available only for phloem-feeding examples from 
the suborder Sternorrhyncha and xylem-feeding examples from the suborder 
Auchenorrhyncha, confounding comparisons. We sequenced genomes of the obligate 
symbionts, Sulcia muelleri and Nasuia deltocephalinicola, of the phloem-feeding 
pest insect, Macrosteles quadrilineatus (Auchenorrhyncha: Cicadellidae). Our 
results reveal that Nasuia-ALF has the smallest bacterial genome yet sequenced 
(112 kb), and that the Sulcia-ALF genome (190 kb) is smaller than that of Sulcia 
in other insect lineages. Together, these symbionts retain the capability to 
synthesize the 10 essential amino acids, as observed for several symbiont pairs 
from xylem-feeding Auchenorrhyncha. Nasuia retains genes enabling synthesis of 
two amino acids, DNA replication, transcription, and translation. Both symbionts 
have lost genes underlying ATP synthesis through oxidative phosphorylation, 
possibly as a consequence of the enriched sugar content of phloem. Shared 
genomic features, including reassignment of the UGA codon from Stop to 
tryptophan, and phylogenetic results suggest that Nasuia-ALF is most closely 
related to Zinderia, the betaproteobacterial symbiont of spittlebugs. Thus, 
Nasuia/Zinderia and Sulcia likely represent ancient associates that have 
co-resided in hosts since the divergence of leafhoppers and spittlebugs >200 Ma, 
and possibly since the origin of the Auchenorrhyncha, >260 Ma.