Oxidative desulfurization (ODS) is a promising method to remove the heterocyclic sulfur compounds from fuel and such process need high-performance catalysts. Polyoxometalates (POMs) have been proven to be excellent catalysts in the ODS reaction, which need to be immobilized on carriers to realize its industrial application. In this work, [beta-SiMo3W9O40](n-) has been loaded on a sustainable cellulose nanofiber (CNF)-based material, which was then calcined at 400 degrees C to form an POM-based composite material. CNF was modified by gamma-(2,3-epoxypropoxy)propyltrimethoxysilane (GPTMS) and polyethyleneimine (PEI) so that the polyanions and protonated PEI could effectively interact with each other; therefore, POM could be well supported on the carrier. The catalytic results showed that in model oil with the sulfur concentration being 2000 ppm, the removal efficiency of dibenzothiophene, benzothiophene, and 4,6-dimethyldibenzothiophene were 99, 89, and 100%, respectively. In addition, infrared spectra analysis indicated the stability of the catalyst after it was recycled. This work provides a new method to obtain effective heterogeneous ODS catalysts by employing an eco-friendly CNF as raw materials.