Post-translational modification of proteins is a ubiquitous mechanism of signal transduction in all kingdoms of life. One such modification is addition of O-linked N-acetylglucosamine to serine or threonine residues, known as O-GlcNAcylation. This unusual type of glycosylation is thought to be restricted to nucleocytoplasmic proteins of eukaryotes and is mediated by a pair of O-GlcNAc-transferase and O-GlcNAc hydrolase enzymes operating on a large number of substrate proteins. Protein O-GlcNAcylation is responsive to glucose and flux through the hexosamine biosynthetic pathway. Thus, a close relationship is thought to exist between the level of O-GlcNAc proteins within and the general metabolic state of the cell. Although isolated apparent orthologues of these enzymes are present in bacterial genomes, their biological functions remain largely unexplored. It is possible that understanding the function of these proteins will allow development of reductionist models to uncover the principles of O-GlcNAc signaling. Here, we identify orthologues of both O-GlcNAc cycling enzymes in the genome of the thermophilic eubacterium Thermobaculum terrenum. The O-GlcNAcase and O-GlcNAc-transferase are co-expressed and, like their mammalian orthologues, localize to the cytoplasm. The O-GlcNAcase orthologue possesses activity against O-GlcNAc proteins and model substrates. We describe crystal structures of both enzymes, including an O-GlcNAcase·peptide complex, showing conservation of active sites with the human orthologues. Although in vitro activity of the O-GlcNAc-transferase could not be detected, treatment of T. terrenum with an O-GlcNAc-transferase inhibitor led to inhibition of growth. T. terrenum may be the first example of a bacterium possessing a functional O-GlcNAc system.