The origin of plastids is best explained by endosymbiotic theory, which dates back to the early 1900s. Three lines of evidence based on protein import machineries and molecular phylogenies of eukaryote (host) and cyanobacterial (endosymbiont) genes point to a single origin of primary plastids, a unique and important event that successfully transferred two photosystems and oxygenic photosynthesis from prokaryotes to eukaryotes. The nature of the cyanobacterial lineage from which plastids originated has been a topic of investigation. Recent studies have focused on the branching position of the plastid lineage in the phylogeny based on cyanobacterial core genes, that is, genes shared by all cyanobacteria and plastids. These studies have delivered conflicting results, however. In addition, the core genes represent only a very small portion of cyanobacterial genomes and may not be a good proxy for the rest of the ancestral plastid genome. Information in plant nuclear genomes, where most genes that entered the eukaryotic lineage through acquisition from the plastid ancestor reside, suggests that heterocyst-forming cyanobacteria in Stanier’s sections IV and V are most similar to the plastid ancestor in terms of gene complement and sequence conservation, which is in agreement with models suggesting an important role of nitrogen fixation in symbioses involving cyanobacteria. Plastid origin is an ancient event that involved a prokaryotic symbiont and a eukaryotic host, organisms with different histories and genome evolutionary processes. The different modes of genome evolution in prokaryotes and eukaryotes bear upon our interpretations of plastid phylogeny.