The phase diagram of absorbed films of O2 molecules on (002) surfaces of graphite has been measured in the range of densities from submonolayer to 1.6 monolayer. This system is particularly interesting because it orders magnetically below 11.9 K for dense monolayer and higher coverages. This magnetic order is observed both through the antiferromagnetic-superstructure-Bragg reflection as well as through the accompanying magnetostrictive distortion which is seen as a splitting of the nuclear Bragg scattering peak. In all, three distinct two-dimensionally ordered phases have been found, each being incommensurate with the graphite surface lattice. Both first-order and continuous transitions have been observed between these phases.