The clean Cu(115) surface shows the regular step arrangement of a vicinal surface in scanning tunneling microscopy. Upon oxygen adsorption the surface reconstructs completely. For temperatures around 500 K during or after oxygen adsorption, pronounced faceting into (104), (014) and (113) facets is observed. Details of the facet structures are analyzed. The (113) facet exhibits an additional reconstruction which can be described as a c(7 x 12) superstructure. The development of Cu-O-Cu atomic chains is suggested to be the driving force for the oxygen-induced surface reconstruction. This reconstruction is reversible; oxygen desorption re-establishes the initial (115) structure.