Development of sustainable biobased fibers is required to displace their fossil-based counterparts, e.g., in textile, nonwoven, or composite applications. Regenerated protein fibers have a potential in this regard if their mechanical properties are improved. Herein, we study for the first time the use of nanocellulose as reinforcement in regenerated protein fibers produced using wet spinning. The influence of cellulose nanocrystals (CNC) incorporated into regenerated casein fibers is examined in terms of mechanical and morphological properties. The influence of different conditions for fiber chemical cross-linking is also investigated. Incorporation of CNC (up to 37.5 wt %) into spin dopes results in a continuous increase of fiber Young's modulus (up to twofold) in the dry state. Both maximum and breaking tenacity of dry fibers are enhanced by CNC, with a maximum at 7.0-10.5 wt % of CNC. When testing after being wetted, both breaking tenacity and Young's modulus of the composite fibers decrease, likely due to weakening of hydrogen bonds between CNC in the presence of water. We also demonstrate that the presence of salt during chemical cross-linking is crucial to produce intact and separated fibers in the yarn.