Pili on the surface of Sulfolobus islandicus are used for many functions, and serve as receptors for certain archaeal viruses. The cells grow optimally at pH 3 and ~80 °C, exposing these extracellular appendages to a very harsh environment. The pili, when removed from cells, resist digestion by trypsin or pepsin, and survive boiling in sodium dodecyl sulfate or 5 M guanidine hydrochloride. We used electron cryo-microscopy to determine the structure of these filaments at 4.1 Å resolution. An atomic model was built by combining the electron density map with bioinformatics without previous knowledge of the pilin sequence-an approach that should prove useful for assemblies where all of the components are not known. The atomic structure of the pilus was unusual, with almost one-third of the residues being either threonine or serine, and with many hydrophobic surface residues. While the map showed extra density consistent with glycosylation for only three residues, mass measurements suggested extensive glycosylation. We propose that this extensive glycosylation renders these filaments soluble and provides the remarkable structural stability. We also show that the overall fold of the archaeal pilin is remarkably similar to that of archaeal flagellin, establishing common evolutionary origins.