CeO2 has been explored as an electro-catalyst in the cathode of lithium-oxygen batteries due to its good performance, especially in the initial discharging stage. In order to fully understand its initial oxygen reduction reaction (ORR), in this work, oxygen and lithium adsorptions and initial ORR on the stoichiometric and reduced CeO2 surfaces were systematically investigated using density functional theory (DFT) calculations. Changes of free energy values and structure parameters of the intermediates and precursors of the initial ORR were also studied to identify the possible reaction paths. It was found that the oxygen atoms are preferably adsorbed on the reduced CeO2 surface, whereas the lithium atoms are preferably adsorbed on both stoichiometric and reduced CeO2 surfaces, therefore, there exists a strong adsorption at the site with high oxygen coordinations. The reduced CeO2 with the surface oxygen vacancies was identified as the most critical surface for the initial oxygen reduction reaction. The path with the lithium adsorption as the first step was identified as the most probable one. A Li3O2 precursor was identified as the most possible initial structure of the catalyst to start the discharging process.