Cell surface proteins of hyperthermophilic Archaea actively participate in intercellular communication, cellular uptake and energy conversion to sustain survival strategies in extreme habitats. Surface (S)-layer glycoproteins, the major component of the S-layers in many archaeal species and the best characterized prokaryotic glycoproteins, have been shown to have a large structural diversity in their glycan compositions. In spite of this, an understanding of the glycosylation of Archaeal proteins other than S-layer is quite limited. Here, the N- glycosylation pattern of cell surface exposed proteins of Sulfolobus solfataricus P2 were analyzed by lectin affinity purification, HPAEC-PAD and multiple mass spectrometry-based techniques. Detailed analysis of SSO1273, one of the most abundant ABC transporters present in the cell surface fraction of S. solfataricus , revealed a novel glycan structure composed of a branched sulfated heptasaccharide, Hex4(GlcNAc)2 plus sulfoquinovose, where Hex is D-mannose and D-glucose. Having one monosaccharide unit more than the glycan of the S-layer glycoprotein of S. acidocaldarius , this is the most complex archaeal glycan structure characterized to date. The SSO1273 protein was found to be heavily glycosylated and all the twenty theoretical N-X-S/T (where X is any amino acid except proline) consensus sequence sites were confirmed. Remarkably, we show that several other proteins in the surface fraction of S. solfataricus are N- glycosylated by the same sulfated oligosaccharide and we identified fifty-six N- glycosylation sites in this subproteome.