Specialty paper (e.g. cigarette paper and battery diaphragm paper) requires extremely high strength properties. The addition of strength agents plays an important role in increasing strength properties of paper. Nanocrystalline cellulose (NCC), or cellulose whiskers, has the potential to enhance the strength properties of paper via improving inter-fibers bonding. This paper was to determine the potential of using carboxylated nanocrystalline cellulose (CNCC) to improve the strength properties of paper made of cellulosic fiber or poly (vinyl alcohol) (PVA) fiber. The results indicated that the addition of CNCC can effectively improve the strength properties. At a CNCC dosage of 0.7%, the tear index and tensile index of the cellulosic paper reached the maximum of 12.8 mN m2/g and 100.7 Nm/g, respectively. More importantly, when increasing the CNCC dosage from 0.1 to 1.0%, the tear index and tensile index of PVA fiber paper were increased by 67.29%, 22.55%, respectively.