The paralytic shellfish poisoning (PSP) toxins, saxitoxin, and its derivatives, are produced by a complex and unique biosynthetic pathway. It involves reactions that are rare in other metabolic pathways, however, distantly related organisms, such as dinoflagellates and cyanobacteria, produce these toxins by an identical pathway. Speculative explanations for the unusual phylogenetic distribution of this metabolic pathway have been proposed, including a polyphyletic origin, the involvement of symbiotic bacteria, and horizontal gene transfer. This study describes for the first time the identity of one gene, sxt1, that is involved in the biosynthesis of saxitoxin in cyanobacteria. It encoded an O-carbamoyltransferase (OCTASE) that was proposed to carbamoylate the hydroxymethyl side chain of saxitoxin precursor. Orthologues of sxt1 were exclusively present in PSP-toxic strains of cyanobacteria and had a high sequence similarity to each other. L. wollei had a naturally mutated sxt1 gene that encoded an inactive enzyme, and was incapable of producing carbamoylated PSP-toxin analogues, supporting the proposed function of Sxt1. Phylogenetic analysis revealed that OCATSE genes were present exclusively in prokaryotic organisms and were characterized by a high rate of horizontal gene transfer. OCTASE has most likely evolved from an ancestral O-sialoglycoprotein endopeptidase from proteobacteria, whereas the most likely phylogenetic origin of sxt1 was an ancestral alpha-proteobacterium. The phylogeny of sxt1 suggested that the entire set of genes required for saxitoxin biosynthesis may spread by horizontal gene transfer.