The TEG gene cluster, a glycopeptide biosynthetic gene cluster that is predicted to encode the biosynthesis of a polysulfated glycopeptide congener, was recently cloned from DNA extracted directly from desert soil. This predicted glycopeptide gene cluster contains three closely related sulfotransferases (Teg12, 13, and 14) that sulfate teicoplanin-like glycopeptides at three unique sites. Here we report a series of structures including: an apo structure of Teg12, Teg12 bound to the desulfated co-substrate 3'-phosphoadenosine 5'-phosphate and Teg12 bound to the teicoplanin aglycone. Teg12 appears to undergo a series of significant conformational rearrangements during glycopeptide recruitment, binding and catalysis. Loop regions that exhibit the most conformational flexibility show the least sequence conservation between TEG sulfotransferases. Site directed mutagenesis guided by our structural studies confirmed the importance of key catalytic residues as well as the importance of residues found throughout the conformationally flexible loop regions.