tmRNA acts to rescue stalled bacterial ribosomes while encoding a peptide tag added trans-translationally to the nascent peptide, targeting it for proteolysis. The permuted gene structure found in a group of cyanobacteria is shown to produce a two-piece mature tmRNA, as had been observed previously for the independently permuted gene of alpha-proteobacteria. The pieces have been mapped onto the gene sequence and aligned for the permuted cyanobacterial tmRNA sequences, including four novel sequences. Structural probing and base pair co-variations support a secondary structure model in which two pairings in the tRNA-like domain hold the two pieces together, and the coding piece bearing the tag reading frame additionally contains a single transient pseudoknot and three other stem-loops. This represents a dramatic reduction in pseudoknot number from the five present in one-piece cyanobacterial tmRNA.