Sialic acid terminates oligosaccharide chains on mammalian and microbial cell surfaces, playing critical roles in recognition and adherence. The enzymes that transfer the sialic acid moiety from cytidine-5′-monophospho-N-acetyl-neuraminic acid (CMP-NeuAc) to the terminal positions of these key glycoconjugates are known as sialyltransferases. Despite their important biological roles, little is understood about the mechanism or molecular structure of these membrane-associated enzymes. We report the first structure of a sialyltransferase, that of CstII from Campylobacter jejuni, a highly prevalent foodborne pathogen. Our structural, mutagenesis and kinetic data provide support for a novel mode of substrate binding and glycosyl transfer mechanism, including essential roles of a histidine (general base) and two tyrosine residues (coordination of the phosphate leaving group). This work provides a framework for understanding the activity of several sialyltransferases, from bacterial to human, and for the structure-based design of specific inhibitors.