The worldwide plastic waste production is steadily increasing, since the use of polymeric materials continues to rise. One area of particular high plastic consumption is food packaging. Flexible and rigid packaging films are typically made from petrochemical-sourced polymers, which are utilized because of their low cost, ductility, melt-processability, and gas barrier properties, but a major downside is their inability to biodegrade in a reasonable time. Packaging-relevant properties of nanocomposites based on polyester-amides (PEAs) are reported, which are chosen on account of their tunable crystallinity, biobased starting materials, and biodegradability. These polymers are synthesized via melt polycondensation of a building block made from caprolactone and 1,4-diaminobutane, with the addition of 1,4-butanediol and dimethyl adipate. The fraction of the amide segment is varied between 25 and 75 mol%. The oxygen transmission rate (O2TR) drops upon increasing the amide content from 1.6 × 105 to 2.9 × 10−4 cm3 m−2 d−1 on account of increasing crystallinity. In order to improve the gas barrier properties further, nanocomposites of the PEAs and 1–10 wt% cellulose nanocrystals (CNCs) are prepared. These nanocomposites have indeed lower O2TR values than the neat PEAs, with reductions of as much as 50% for a CNC content of 10 wt%.