The aim of this study was to explore the high value-added utilization way of wasting paper. The waste corrugated carton, waste office paper and waste packaging cardboard were used as materials to make nano-cellulose with the sulfuric acid method. The H2O2-oxidized starch adhesives were prepared and modified by adding different amounts of nano-cellulose. The effects of material type and addition amount of nano-cellulose on the adhesive properties of oxidized starch were studied. The addition of nano-cellulose improved the properties of the oxidized starch adhesive. The best performance of the oxidized starch adhesives was obtained when the nano-cellulose content was 1% . Under the above condition, the viscosity, the drying speed and the bonding strength all reached their maximum values. The viscosity of the oxidized starch adhesive was 0.217 Pa·s, the water loss rate at 4 h was 43.43% and the maximum bonding strength was 1.243 MPa. Compared with the oxidized starch adhesives without nano-cellulose addition, these properties were improved by 5.8%, 6.78% and 17.26%, respectively. In conclusion, the effects of nano-cellulose prepared with different materials on the properties of the oxidized starch adhesives were obtained, and a method was found for the recycling of waste packaging paper.