Utilization of bacterial nanocellulose (BNC) for large-scale applications is restricted by low productivity in static cultures and by the high cost of the medium. Fiber sludge, a waste stream from pulp and paper mills, was enzymatically hydrolyzed to sugar, which was used for the production of BNC by the submerged cultivation of Komagataeibacter xylinus. Compared with a synthetic glucose-based medium, the productivity of purified BNC from the fiber sludge hydrolysate using shake-flasks was enhanced from 0.11 to 0.17 g/(L × d), although the average viscometric degree of polymerization (DPv) decreased from 6760 to 6050. The cultivation conditions used in stirred-tank reactors (STRs), including the stirring speed, the airflow, and the pH, were also investigated. Using STRs, the BNC productivity in fiber-sludge medium was increased to 0.32 g/(L × d) and the DPv was increased to 6650. BNC produced from the fiber sludge hydrolysate was used as an additive in papermaking based on the chemithermomechanical pulp (CTMP) of birch. The introduction of BNC resulted in a significant enhancement of the mechanical strength of the paper sheets. With 10% (w/w) BNC in the CTMP/BNC mixture, the tear resistance was enhanced by 140%. SEM images showed that the BNC cross-linked and covered the surface of the CTMP fibers, resulting in enhanced mechanical strength.