In this work, we present the development of bionanocomposite coatings on poly(ethylene terephthalate) (PET) with outstanding oxygen barrier properties. Pullulan and graphene oxide (GO) were used as main polymer phase and nanobuilding block (NBB), respectively. The oxygen barrier performance was investigated at different filler volume fractions (ϕ) and as a function of different relative humidity (RH) values. Noticeably, the impermeable nature of GO was reflected under dry conditions, in which an oxygen transmission rate (OTR, mL·m−2·24 h−1) value below the detection limit of the instrument (0.01 mL·m−2·24 h−1) was recorded, even for ϕ as low as 0.0004. A dramatic increase of the OTR values occurred in humid conditions, such that the barrier performance was totally lost at 90% RH (the OTR of coated PET films was equal to the OTR of bare PET films). Modelling of the experimental OTR data by Cussler’s model suggested that the spatial ordering of GO sheets within the main pullulan phase was perturbed because of RH fluctuations. In spite of the presence of the filler, all the formulations allowed the obtainment of final materials with haze values below 3%, the only exception being the formulation with the highest loading of GO (ϕ ≈ 0.03). The mechanisms underlying the experimental observations are discussed.