Deinking is a key step in the recycling of waste paper. To address the problems of traditional chemical deinking, which generates large amounts of highly polluted wastewater and increases environmental pressure and treatment costs, as well as the issues of insufficient pulp brightness and high effective residual ink concentration (ERIC), a study on enzymatic deinking of old newsprint paper (ONP) was conducted. By optimizing the ratio of lipase, cellulase, amylase, and xylanase, a composite enzyme preparation for ONP deinking was successfully developed, and the corresponding deinking process was established. The composition of the composite enzyme preparation is as follows: Lipase 1.5 U/g oven-dried pulp (ODP), Cellulase 2 U/g ODP, Amylase 1.5 U/g ODP, and Xylanase 2 U/g ODP. When the composite enzyme preparation was used for enzymatic deinking, compared with chemical deinking, the brightness increased by 3.52% ISO, ERIC decreased by 9.12 ppm, and the physical properties of the paper were improved to varying degrees. The deinking efficiency was significantly superior to that of chemical deinking, while the usage of chemical reagents was effectively reduced. Fourier transform infrared spectroscopy (FTIR) and scanning electron microscopy (SEM) were further used to investigate the effect of the composite enzyme on fiber structure and its possible synergistic mechanism: the surface structure and hydrogen bond network of fibers were altered, thereby reducing the content of chromophores such as hydroxyl, carbonyl, and benzene ring groups as well as residual lignin, and facilitating the separation of ink from the fiber surface. This study provides support for the development of an environmentally friendly waste paper recycling process and contributes to promoting the sustainable development of the papermaking industry.