The presence of the crystalline regions in poly(vinyl alcohol) coating films acts as barrier clusters forcing the gas molecules to diffuse in a longer pathway in the amorphous region of the polymer, where diffusivity and solubility are promoted in comparison. Evaluating the influence of crystalline regions on the oxygen barrier property of a semi-crystalline polymer is thus essential to prepare better coating films. Poly(vinyl alcohol) coating films with varying induced crystallinity were prepared on a polyethylene terephthalate (PET) substrate by drying at different annealing temperatures for 10 min. The coating films were first delaminated from the PET substrate and then characterized using Fourier transform infrared (FTIR) spectroscopy, differential scanning calorimetry (DSC), and X-ray diffraction (XRD) techniques to determine and confirm the induced percentage of crystallinity. The barrier performance of the coating films, i.e., the oxygen transmission rate (OTR), was measured at room temperature. Results showed a decrease in the OTR values of poly(vinyl alcohol) film with an increase in the degree of crystallinity of the polymer matrix. Tortuosity-based models, i.e., modified Nielsen models, were adopted to predict the barrier property of the semi-crystalline PVOH film with uniform or randomly distributed crystallites. A modified Nielsen model for orderly distributed crystallites with an aspect ratio of 3.4 and for randomly distributed crystallites with an aspect ratio of 10.4 resulted in a good correlation with the experimental observation. For the randomly distributed crystallites, lower absolute average relative errors of 4.66, 4.45, and 5.79% were observed as compared to orderly distributed crystallites when the degree of crystallinity was obtained using FTIR, DSC, and XRD data, respectively.