The use of cellulose nanofibrils (CNF) as reinforcements in polymers strongly increased in the last years, due to its high elastic modulus and tensile strength, low permeability to oxygen, allied to its low density, low cost, renewability and abundance. Cellulose is highly hydrophilic while most polymeric matrices are hydrophobic, turning the dispersion of nanofibrils expressive challenge during the development of these materials. Many attempts deal with the chemical modification of cellulose nanostructures in order to avoid irreversible agglomeration after drying. There are few studies in literature that show cellulose nanofibrils acting as effective nucleating agents for some biopolymers. The purpose of this study was to develop nanocomposites of a biodegradable poly(hydroxybutyrate-co-hydroxyvalerate) (PHBV) matrix reinforced with eucalyptus cellulose nanofibrils through melt processing. The CNF were mixed in aqueous solution in the presence of different physical modifiers, such as: poly(ethylene oxide) (PEO), ethylene copolymer modified with 6 wt% of acrylic acid (PEAA) and maleic anhydride (MA), and then freeze-dried and milled for feeding with PHBV in a torque rheometer. The influence of CNF before and after the surface modification on the crystallinity index and crystallization rate of PHBV, as well as the thermal, rheological and morphological properties of the nanocomposites were evaluated. From these analyses, it can be concluded that the CNF acted as a nucleating agent for PHBV, accelerating its crystallization. The thermal stability of the PHBV changed according to the type of surface modification of CNF, as revealed by thermogravimetry.