Sewage fine sieved fraction (FSF) is a heterogeneous substrate consisting of mainly toilet paper fibers sequestered from municipal raw sewage by a fine screen. In earlier studies, a maximum biodegradation of 62% and 57% of the sewage FSF was found under thermophilic (55 °C) and mesophilic (35 °C) conditions, respectively. In order to research this limited biodegradability of sewage FSF, this study investigates the biodegradation of different types of cellulosic fibers-based hygiene papers including virgin fibers based toilet paper (VTP), recycled fiber based toilet paper (RTP), virgin pulp for paper production (VPPP) as a raw material, as well as microcrystalline cellulose (MCC) as a kind of fiberless reference material. The anaerobic biodegradation or digestibility tests were conducted under thermophilic and mesophilic conditions. Results of the experiments showed different biomethane potential (BMP) values for each tested cellulose fiber-based substrate, which might be associated with the physical characteristics of the fibers, type of pulping, presence of lignin encrusted fibers, and/or the presence of additive chemicals and refractory compounds. Higher hydrolysis rates (K_h), higher specific methane production rates (SMPR) and shorter required incubation times to achieve 90% of the BMP (t_90%CH₄), were achieved under thermophilic conditions for all examined substrates compared to the mesophilic ones. Furthermore, the biodegradability of all employed cellulose fiber-based substrates was in the same range, 38-45%, under both conditions and less than the observed FSF biodegradability, i.e. 57-62%. MCC achieved the highest BMP and biodegradability, 86-91%, among all cellulosic substrates.