Using a giant radio telescope in Germany, water molecules have been detected in a galaxy about 11 billion light-years away. This means that there was already detectable amounts of water in our universe when it was only less than four billion years old, which also means that there must have already been enough supernovas by then to create plenty of oxygen.
Like many other cosmological objects from the far past, the detection was aided thanks to the gravitational lensing provided by a foreground galaxy. Detection was also aided by the fact that the water effectively acted as a gigantic laser powered by the supermassive black hole in the center of the galaxy, except that radio waves are emitted instead of visible light.