This study reports on the development and characterization of organic recyclable high-oxygen-barrier multilayer films based on different commercial polyhydroxyalkanoate (PHA) materials, including a blend with commercial poly(butylene adipate-co-terephthalate) (PBAT), which contained an inner layer of cellulose nanocrystals (CNCs) and an electrospun hot-tack adhesive layer of poly(3-hydroxybutyrate-co-3-hydroxyvalerate) (PHBV) derived from cheese whey (CW). As a result, the full multilayer structures were made from bio-based and/or compostable materials. A characterization of the produced films was carried out in terms of morphological, optical, mechanical, and barrier properties with respect to water vapor, limonene, and oxygen. Results indicate that the multilayer films exhibited a good interlayer adhesion and contact transparency. The stiffness of the multilayers was generally improved upon incorporation of the CNC interlayer, whereas the enhanced elasticity of the blend was reduced to some extent in the multilayer with CNCs, but this was still much higher than for the neat PHAs. In terms of barrier properties, it was found that 1 µm of the CNC interlayer was able to reduce the oxygen permeance between 71% and 86%, while retaining the moisture and aroma barrier of the control materials.