Free-standing and flexible biocomposite films formed by a polyaleuritate matrix and nanocellulose fillers (i.e., cellulose nanofibrils) have been fabricated by a sustainable process. For this, 9,10,16-trihydroxyhexadecanoic (aleuritic) acid from shellac and nanocellulose were blended at different ratios in water through a sonication process. Polymerization of the polyhydroxylated fatty acid into polyaleuritate was induced by a solvent-free, melting polycondensation reaction in the oven. These biocomposites were characterized to evaluate their chemical (by ATR-FTIR spectroscopy) and physical (e.g., density, thermal stability, rigidity, gas permeability, surface energy, etc.) properties. The compatibility between the polyester matrix and the polysaccharide fillers was excellent due to the interaction by H bonds of the polar groups of both components. The addition of nanocellulose increased all determined mechanical parameters as well as the wettability and the barrier properties, while the thermal stability and the water uptake were determined by the polyaleuritate matrix. The physical properties of these biocomposites were compared to those of petroleum-based plastics and bio-based polymers, indicating that the developed materials can represent a sustainable alternative for different applications such as packaging.