The influence of nanofibrillated cellulose (NFC) was investigated as a reinforcing agent to improve strength properties of papersheets fabricated from recycled pulp fibers of mixtures of old newspapers, old magazines, and old corrugated cardboards. To determine the effects of the NFC on the mechanical and physical properties of the recycled pulp papers, cellulose nanofibrils (NFC) were isolated from wheat straw, pretreated chemically and enzymatically (NFC-OX), and then added to the bulk suspensions of papermaking pulp slurries at various percentages. The electrokinetic and drainage properties of the pulps and the mechanical and physical properties of the papersheets were analyzed and compared. As expected, the addition of NFC/NFC-OX significantly increased the strength properties of papers. Papers containing 4% of NFC-OX (periodate pretreated) presented higher increases in tensile index (43%) and burst index (59.3%) than other papers. However, a high addition of NFC/NFC-OX increased the water retention, which is undesirable for papermaking. Hence, with optimum selection of NFC/NFC-OX and process conditions, higher mechanical properties could be acquired without increasing drainage rate. Compared to the other pretreated NFC/NFC-OX types, sodium-periodate-oxidized NFC-OX samples significantly increased the mechanical properties of the papers fabricated from the recycled pulps.