Regular crystalline surface layers (S-layers) are widespread among prokaryotes and probably represent the earliest cell wall structures. S-layer genes have been found in approximately 400 different species of the prokaryotic domains bacteria and archaea. S-layers usually consist of a single (glyco-)protein species with molecular masses ranging from about 40 to 200 kDa that form lattices of oblique, tetragonal, or hexagonal architecture. The primary sequences of hyperthermophilic archaeal species exhibit some characteristic signatures. Further adaptations to their specific environments occur by various post-translational modifications, such as linkage of glycans, lipids, phosphate, and sulfate groups to the protein or by proteolytic processing. Specific domains direct the anchoring of the S-layer to the underlying cell wall components and transport across the cytoplasma membrane. In addition to their presumptive original role as protective coats in archaea and bacteria, they have adapted new functions, e.g., as molecular sieves, attachment sites for extracellular enzymes, and virulence factors.