Developing chrome-free and sustainable tanning agents is extremely important to the sustainability of the leather industry. Herein, we have synthesized an Al-Zr-oligosaccharides tanning agent via a simultaneous degradation and oxidation of cellulose in waste paper. The influence of the temperature and the concentrations of AlCl3 and H2O2 during the synthesis were thoroughly investigated on the properties of the tanning agent and the leather produced. The synthesis temperature and the concentration of AlCl3 were the factors primarily affecting the effective depolymerization of cellulose. They controlled the conversion of waste paper into oligosaccharides with an appropriate molecular weight to efficiently penetrate the leather matrix. In parallel, the H2O2 concentration substantially influenced the tanning performance of the Al-Zr-oligosaccharides, diminishing the chromaticity of the tanning liquid via oxidation and promoting the conversion of C2/C3/C6-OH moieties into -CHO/-COOH. These functional groups increased the surface charge of the oligosaccharides allowing more effective coordination with Al/Zr, which facilitated the penetration of Al/Zr species into the leather matrix. Once inside the leather matrix, Al and Zr were released and reacted with the collagen fibers in leather, which resulted in effective leather tanning. The process optimization revealed that up to 57% of waste paper could be converted into a low-chromaticity (4350 AU) liquid hydrolysate with the synthesis conducted at 177 °C in a system comprising 47 mM AlCl3 and 5 vol% H2O2. The application of this liquid for tanning provided leather with a shrinkage temperature (86.5 °C) sufficiently high for commercial applications. These excellent results, combined with the intrinsic green nature of our approach, exemplify a step forward to simultaneously reduce pollution and hazards in leather industries giving a second life to waste paper.