tmRNA employs both tRNA-like and mRNA-like properties as it rescues stalled bacterial ribosomes, while targeting the defective mRNA and incomplete nascent protein for degradation. We describe variation of the tmRNA gene (ssrA) and how it informs tmRNA structure and function. Endosymbiont tmRNAs tend to lose secondary structure and length in the mRNA-like region as nucleotide composition drifts with that of the whole genome. A dramatic gene structure variation is circular permutation, which produces two-piece tmRNAs in three bacterial lineages; new sequences blur these lineages. We present evidence that Sinorhizobium two-piece tmRNA retains the 5'-triphosphate of transcriptional initiation and predict a new structure at the 5' end of cyanobacterial two-piece tmRNA precursor. ssrA is a target for some mobile DNAs and a passenger on others. It has been found interrupted (but not functionally disrupted) by mobile elements such as group I introns, genomic islands and palindromic elements. The alphaproteobacterial permuted genes are significantly less frequently interrupted by genomic islands than are their standard counterparts, yet are a hotspot for insertion or swapping of rickettsial palindromic elements, in contrast to other rickettsial loci that show steady decay of a single ancestral element. Bacteriophages, plasmids and genomic islands can carry tmRNA genes; we describe a native bacterial ssrA disrupted by insertion of a genomic island that carries its own ssrA, a genome encoding both one- and two-piece tmRNA, and a phage encoding a tmRNA variant lacking the mRNA-like function, which may counteract host tmRNA during infection.