The cell-surface glycoprotein of Halobacteria contains oligosaccharides of the type Glc4----1GlcA4----1GlcA4----1GlcA (where GlcA indicates glucuronic acid) with a sulfate group attached to each of the GlcA residues. We report here that in addition to this cell-surface glycoprotein, the halobacterial flagellar proteins (recently described by Alam, M., and Oesterhelt, D. (1984) J. Mol. Biol. 176, 459-475) also contain the same type of sulfated oligosaccharides. These flagellins have the following features. All of the individual flagellar proteins contain identical sulfated saccharide moieties linked to the amido nitrogen of Asn through a Glc residue (the novel type of N-glycosidic linkage that has been found in the cell-surface glycoprotein from Halobacteria (Wieland, F., Heitzer, R., and Schaefer, W. (1983) Proc. Natl. Acad. Sci. U.S.A. 80, 5470-5474)). The amino acid sequence of one carbohydrate-binding region is Gln-Ala-Ala-Gly-Ala-Asp-Asn-Jle-Asn-Leu-Thr-Lys. This surrounding sequence CHO is consistent with the general formula Asn-X-Thr(Ser), common to all N-linked glycopeptides determined so far. Biosynthesis of flagellar glycoconjugates involved sulfated oligosaccharides linked to dolichol monophosphate. The individual glycoproteins making up the flagella are structurally closely related to one another.