The chemisorption of oxygen on Cu(111) has been studied by scanning tunneling microscopy. Two hitherto unknown well ordered oxygen induced reconstructions with extremely large unit cells, 29 and 44 times the 1 x 1 surface unit, are presented. The reconstructions emerge as coincidence lattices between the 1 x 1 surface lattice and a hexagonal substructure, which is associated with the (111) plane of Cu2O.