The demand for eco-friendly packaging materials has urged researchers to look for alternatives to petroleum-based polymers. In this regard, paper-based products have turned out to be a promising choice; however, their weak resistance to water has limited their application. The use of various additives to enhance paper’s moisture resistance is a common practice. However, considering the growing global agenda for sustainable development, the search for new bio-based paper additives has become increasingly important. This study investigated the potential synergistic impact of the addition of nanofibrillated cellulose (NFC) and chitosan additives (CHIT) to different fiber combinations to improve paper’s properties, in particular, their wet strength. The efficacy of the additive application order was examined and was found to be crucial in achieving the desired outcomes. The results showed that incorporating CHIT after NFC enhanced the paper’s tensile and burst indicators, as well as the paper stretch in the dry state, by 35–70%, 35–55%, and 20–35%, respectively. In addition, the tensile index and stretch in the wet state improved 9–13 times and 2.5–5.5 times over, respectively. The air permeability decreased 2.5–12 times over. These findings demonstrate that the sequential addition of the NFC and CHIT additives yield a greater enhancement of paper’s properties than using each additive separately.