Composite materials made of cellulose fibers and spin crossover micro-particles were investigated by magnetic measurements and dynamic mechanical analysis (DMA). The storage modulus of the cellulose handsheet (0.6 GPa at room T) is significantly enhanced in the composite (1.7 GPa). The latter also displays a reversible increase of ca. 10% when switching the magnetic spin state of the particles from the low spin (LS) to the high spin (HS) form. Around the spin transition temperature a loss modulus peak is also observed, highlighting the strong viscoelastic coupling between the particles and the cellulose matrix. These results pave the way for the development of a novel family of actuator materials based on spin crossover-polymer composites.