This study aims to prepare and examine the properties of poly(vinyl alcohol)/casein (PVA/CAS) based films reinforced with cellulose nanocrystals (NC), which can be presented as an alternative to petroleum-based polymer packaging materials. PVA/CAS and 0.5–1–3–5 wt% NC containing PVA/CAS biocomposite films were prepared by solution casting method. Afterward, the 1NC film, which exhibited the best mechanical properties, was crosslinked with various amounts of glyoxal. Structural, morphological (polarized optical microscope), mechanical (tensile), thermal (differential scanning calorimetry, thermogravimetric analysis), contact angle, and water vapor transmission rate (WVTR) properties of the samples were investigated. The 1NC film exhibited the highest tensile strength (TS) and elongation values in PVA/CAS/NC films, and its mechanical properties decreased due to agglomeration with increasing NC amount. As expected, crosslinking improved the TS. The thermal stability of the PVA/CAS film was generally improved with the addition of NC and crosslinking. The high WVTR value of the PVA/CAS film decreased with the addition of NC and the 1NC film presented the lowest value. Thanks to the complex structure formed as a result of crosslinking and the reduced free volume, the WVTR of the 1NC film has reduced. The results showed that PVA/CAS-based films with good mechanical properties and water vapor barrier are promising as packaging materials.