A significant increase in the consumption of recycled fiber products has been observed worldwide, and the industry is forced to solve the challenges of recycled fiber quality and add strength agents and/or virgin fibers to reach sufficient properties. In order to investigate whether the mechanical and air permeability properties of waste fiber (WF) material can be significantly improved by adding wood kraft fibers (KF), hemp soda fibers (HF), and ammonium persulfate oxidated cellulose nanofibrils (CNF), different fiber blends were prepared and tested. Results revealed the excellence of hemp fibers over wood fibers regarding the improvement of WF products. The results of WF after the addition of 10% mixed fibers (KF + HF) were higher than the results of a 50% KF addition. The impact of CNF depended on fiber composition and properties. A formula for modeling the CNF impact on different fiber compositions was proposed. Obtained fiber material samples showed suitability for home composting, thus contributing to the goals of the European Green Deal regarding reducing landfill waste and the development of cleaner products.