Conservation of paper-based materials, namely, manuscripts, includes repair of tears, gap filling, consolidation, and fixation, which requires the use of adhesives. The adhesive in use for these purposes should be compatible with the chemical and physical properties of paper and should present good aging characteristics. In this study, we conducted a set of experiments with paper samples on which fructan-based biopolymer Halomonas levan (Hlevan) was applied for the first time and compared with glucan-based adhesive starch. Adhesive-applied samples were initially prepared by the application of different historical recipes of sizing and ink. Then, they underwent accelerated thermal aging. Chemical and physical changes of paper samples (crystallinity, pH, and color) were analyzed. Finally, Principal Component Analysis was performed to identify dominating factors affecting sample behavior with applied adhesives. This study demonstrates the aging characteristics of Hlevan on cellulose-based materials. The results showed that there is a color shift from blue to yellow for all samples after aging, but it is more pronounced for some samples with Hlevan. In addition, Hlevan is slightly less acidic than starch in all cases and acted as a plasticizer for a specific kind of sizing material. The methodology of this research is also efficacious in terms of understanding the interaction of paper media with the adhesives and their effects on aging.