The interaction of potassium and oxygen, individually and as coadsorbates with graphite, was studied experimentally and theoretically. In the experiments the sticking of oxygen was investigated at different K coverages. The extremely low sticking coefficient for chemisorption/dissociation of dioxygen on clean graphite is contrasted by the high sticking coefficient for even very dilute potassium overlayers. KO2 and K2O complexes are identified as early precursors to CO2 formation from coadsorbed potassium and oxygen. The K-O complexes formed on the surface and their transformations (as a function of increasing temperature) were followed by thermal desorption spectroscopy (TDS) and electron energy loss spectroscopy (HREELS). A theoretical study based on the tight-binding method indicates why the presence of potassium facilitates the chemisorption of dioxygen, whose sticking coefficient on clean graphite is otherwise very small. It is suggested that the potassium promotion effect is a very local one and that formation of a K-O2 surface complex is the first step in graphite oxidation. The strongly preferred adsorption site for O2 on a K-covered surface is on top of a potassium atom with no interaction to the graphite layer. From there the dioxygen molecule can dissociate into oxygen atoms. The stabilizing K-O2 interaction can be traced to a localized sp-hybrid available for bonding to O2 and the fact that the graphite pi system is not distorted upon chemisorption of O2 via the potassium spacer. Concerning the favored adsorption sites for the individual species, a slight preference is deduced for K above a hexagon (6-fold symmetry site), while O and O2 more strongly favor a position on top of a carbon atom (O2 in a bent end-on approach) for the undamaged surface. Surface defects, however, figure prominently in stabilizing the oxygen species and also a potassium atom in the defect area.