Bacterial cellulose nanocrystals (BCNCs) obtained by enzymatic hydrolysis have been loaded in pullulan biopolymer for use as nanoparticles in the generation of high-oxygen barrier coatings intended for food packaging applications. Bacterial cellulose (BC) produced by Komagataeibacter sucrofermentans was hydrolyzed by two different enzymatic treatments, i.e., using endo-1,4-β-glucanases (EGs) from Thermobifida halotolerans and cellulase from Trichoderma reesei. The hydrolytic activity was compared by means of turbidity experiments over a period of 145 h, whereas BCNCs in their final state were compared, in terms of size and morphology, by atomic force microscopy (AFM) and dynamic light scattering (DLS). Though both treatments led to particles of similar size, a greater amount of nano-sized particles (≈250 nm) were observed in the system that also included cellulase enzymes. Unexpectedly, transmission electron microscopy (TEM) revealed that cellulose nanoparticles were round-shaped and made of 4–5 short (150–180 nm) piled whiskers. Pullulan/BCNCs nanocomposite coatings allowed an increase in the overall oxygen barrier performance, of more than two and one orders of magnitude (≈0.7 mL·m⁻²·24 h⁻¹), of pure polyethylene terephthalate (PET) (≈120 mL·m⁻²·24 h⁻¹) as well as pullulan/coated PET (≈6 mL·m⁻²·24 h⁻¹), with no significant difference between treatments (hydrolysis mediated by EGs or with the addition of cellulase). BCNCs obtained by enzymatic hydrolysis have the potential to generate high oxygen barrier coatings for the food packaging industry.