In the present study, a multilayer, high-barrier, thin blown film based on a polybutylene adipate terephthalate (PBAT) blend with polyhydroxyalkanoate (PHA), and composed of four layers including a cellulose nanocrystal (CNC) barrier layer and an electrospun poly(3-hydroxybutyrate-co-3-hydroxyvalerate) (PHBV) hot-tack layer, was characterized in terms of the surface roughness, surface tension, migration, mechanical and peel performance, barrier properties, and disintegration rate. The results showed that the film exhibited a smooth surface. The overall migration tests showed that the material is suitable to be used as a food contact layer. The addition of the CNC interlayer had a significant effect on the mechanical properties of the system, drastically reducing the elongation at break and, thus, the flexibility of the material. The film containing CNCs and electrospun PHBV hot-tack interlayers exhibited firm but not strong adhesion. However, the multilayer was a good barrier to water vapor (2.4 ± 0.1 × 10−12 kg·m−2·s−1·Pa−1), and especially to oxygen (0.5 ± 0.3 × 10−15 m3·m−2·s−1·Pa−1), the permeance of which was reduced by up to 90% when the CNC layer was added. The multilayer system disintegrated completely in 60 days. All in all, the multilayer system developed resulted in a fully compostable structure with significant potential for use in high-barrier food packaging applications.