Proteinaceous surface layers (S-layers) are highly ordered, crystalline structures commonly found in prokaryotic cell envelopes that augment their structural stability and modify interactions with metals in the environment. While mineral formation associated with S-layers has previously been noted, the mechanisms were unconstrained. Using Sulfolobus acidocaldarius a hyperthermophilic archaeon native to metal-enriched environments and possessing a cell envelope composed only of a S-layer and a lipid cell membrane, we describe a passive process of iron phosphate nucleation and growth within the S-layer of cells and cell-free S-layer "ghosts" during incubation in a Fe-rich medium, independently of metabolic activity. This process followed five steps: (1) initial formation of mineral patches associated with S-layer; (2) patch expansion; (3) patch connection; (4) formation of a continuous mineral encrusted layer at the cell surface; (5) early stages of S-layer fossilization via growth of the extracellular mineralized layer and the mineralization of cytosolic face of the cell membrane. At more advanced stages of encrustation, encrusted outer membrane vesicles are formed, likely in an attempt to remove damaged S-layer proteins. The S-layer structure remains strikingly well preserved even upon the final step of encrustation, offering potential biosignatures to be looked for in the fossil record.