The adsorption and co-adsorption of lithium and oxygen at the surface of rutile-like manganese dioxide ([small beta]-MnO2), which are important in the context of Li-air batteries, are investigated using density functional theory. In the absence of lithium, the most stable surface of [small beta]-MnO2, the (110), adsorbs oxygen in the form of peroxo groups bridging between two manganese cations. Conversely, in the absence of excess oxygen, lithium atoms adsorb on the (110) surface at two different sites, which are both tri-coordinated to surface oxygen anions, and the adsorption always involves the transfer of one electron from the adatom to one of the five-coordinated manganese cations at the surface, creating (formally) Li+ and Mn3+ species. The co-adsorption of lithium and oxygen leads to the formation of a surface oxide, involving the dissociation of the O2 molecule, where the O adatoms saturate the coordination of surface Mn cations and also bind to the Li adatoms. This process is energetically more favourable than the formation of gas-phase lithium peroxide (Li2O2) monomers, but less favourable than the formation of Li2O2 bulk. These results suggest that the presence of [small beta]-MnO2 in the cathode of a non-aqueous Li-O2 battery lowers the energy for the initial reduction of oxygen during cell discharge.