It is generally accepted that the plastids arose from a cyanobacterial ancestor, but the exact phylogenetic relationships between cyanobacteria and plastids are still controversial. Most studies based on partial 16S rRNA sequences suggested a relatively late origin of plastids within the cyanobacterial divergence. In order to clarify the exact relationship and divergence order of cyanobacteria and plastids, we studied their phylogeny on the basis of nearly complete 16S rRNA gene sequences. The data set comprised 15 strains of cyanobacteria from different morphological groups, 1 prochlorophyte, and plastids belonging to 8 species of plants and 12 species of diverse algae. This set included three cyanobacterial sequences determined in this study. This is the most comprehensive set of complete cyanobacterial and plastidial 16S rRNA sequences used so far. Phylogenetic trees were constructed using neighbor joining and maximum parsimony, and the reliability of the tree topologies was tested by different methods. Our results suggest an early origin of plastids within the cyanobacterial divergence, preceded only by the divergence of two cyanobacterial genera, Gloeobacter and Pseudanabaena.