The 198-amino-acid in-frame insertion in the gyrA gene of Mycobacterium xenopi is the smallest known naturally occurring active protein splicing element (intein). Comparison with other mycobacterial gyrA inteins suggests that the M. xenopi intein underwent a complex series of events including (i) removal of 222 amino acids that encompass most of the central intein domain, and (ii) addition of a linker of unrelated residues. This naturally occurring genetic rearrangement is a representative characteristic of the taxon. The deletion process removes the conserved motifs involved in homing endonuclease activity. The linker insertion represents a structural requirement, as its mutation resulted in failure to splice. The M. xenopi GyrA intein thus provides a paradigm for a minimal protein splicing element.