The conservation of historical paper objects with high cultural value is an important societal task. Papers that have been severely damaged by fire, heat, and extinguishing water, are a particularly challenging case, because of the complexity and severity of damage patterns. In-depth analysis of fire-damaged papers, by means of examples from the catastrophic fire in a 17th-century German library, shows the changes, which proceeded from the margin to the center, to go beyond surface charring and formation of hydrophobic carbon-rich layers. The charred paper exhibits structural changes in the nano- and micro-range, with increased porosity and water sorption. In less charred areas, cellulose is affected by both chain cleavage and cross-linking. Based on these results and conclusions with regard to adhesion of auxiliaries, a stabilization method is developed, which coats the damaged paper with a thin layer of cellulose nanofibers. It enables the reliable preservation of the paper and—most importantly—retrieval of the contained historical information: the nanofibers form a flexible, transparent film on the surface and adhere strongly to the damaged matrix, greatly reducing its fragility, giving it stability, and enabling digitization and further handling.