In fuel cells, the oxygen reduction reaction (ORR) at the cathode plays a crucial role in their performance. High cost, low abundance, catalyst poisoning, and poor durability of the pioneering ORR catalyst Pt make it less desirable for commercial fuel cells. Herein, we demonstrate a greener process to synthesize CeO2 nanostructures by varying reaction parameters in a single-step solvothermal route and provide a detailed mechanism for the formation of CeO2 nanostructures with different shapes. The shape and size of the CeO2 nanostructures such as hollow/solid spheres, triangular flakes, nanotubes, and flower-like structures result in a strong effect on their ORR activity. A normalized effect of effective surface area and oxygen vacancies in CeO2 nanostructures is found to govern the ORR activity order. Among the CeO2 nanostructures, hollow spheres exhibit the best ORR activity with a four-electron reduction pathway. Moreover, they show comparable ORR activity and outstanding stability as well as methanol fuel tolerance and are a substitute for Pt/C.