Cellulose nanocrystals (CNC) and microcrystals (CMC) were selected as reinforcing fillers for poly(2-ethyl-2-oxazoline), a water-soluble thermoplastic adhesive widely used in the restoration of oil paintings. Thin composite films containing 5, 10, and 30 wt% of CNC or CMC were produced by solution mixing and casting. UV-vis spectroscopy showed how CNC preserved the adhesive transparency even at the highest CNC content, while for CMC, a progressive loss of transparency was observed. Thermal analysis evidenced a progressive increase of the glass transition temperature of the polymer matrix induced by CNC, while no effects were observed for CMC. Both micro- and nanocellulose were able to improve the elastic modulus and reduce the thermal expansion coefficient and creep compliance of the adhesive, with effects more pronounced for CNC nanoparticles. Finally, single-lap shear test on bonded ancient oil painting substrates confirmed the improved dimensional stability of the joint imparted by CNC in the adhesive under both quasi-static and creep conditions.