Extending the limits of paper recycling by increasing the number of recycling cycles results in decreased mechanical properties due to the irreversible hornification of cellulose fibers. This process alters the fiber structure and properties because of the repeated chemical and mechanical treatments that occur during wetting and drying. As a result, poor tensile strength is the main source of customer complaints to paper manufacturers. Cellulose nanofibers (CNF) from bleached eucalyptus and pine pulps were investigated as potential strength additives because of their proven contribution to interfiber bonding. These results were compared to the results obtained using different families of strength additives. The effects on the mechanical properties of recycled old corrugated containers were studied by measuring bursting, tensile, and short span compressive strength. Cellulose nanofibers and cationic polyacrylamide (cPAM) improved the mechanical strength properties when they were added at doses around 4 wt.%. A combination of CNF and cPAM was also tested. The effects of the combined additives were not as high as expected compared to the results achieved individually. The CNF from pine pulp resulted in the highest increase in bursting index when combined with cPAM, achieving an increase of over 93%. The combination of CNF from eucalyptus pulp and cPAM increased the bursting index over 60%.