Cerium oxide (CeO2) nanostructures are an interesting metal oxide in catalysis owing to their unique redox properties and high mobility of oxygen vacancies at the surface. CeO2 nanostructure was synthesized via a green route using an aqueous extract of Picrasma quassioides bark. Formation of ceria nanostructures were monitored by UV-Vis absorption spectroscopy and Fourier transform infrared spectroscopy (FTIR). Annealing temperature-dependent crystallite size and lattice strain on the X-ray peak broadening of the CeO2 nanostructures was determined by the size-strain plots. The application of the green synthesized CeO2 nanostructures for the catalytic degradation of methylene blue by NaBH4 was carried out. We demonstrated that the catalytic decomposition rate was gradually improved due to the increase of annealing temperature of CeO2 nanostructure, and obtained highest performance at 600 °C annealed sample. This is because of the significantly improved crystallinity of CeO2 nanostructure at higher temperature, leading in a low density of crystalline defects and wide distribution of nanostructure with a large surface area to provide more active electrons (e-) for the decomposition of dye.