Recent studies of the colour gauge theory of the strong interactions indicate that nuclear matter will transform into quark matter when heated or compressed by relatively modest amounts. Such matter almost certainly existed in the early Universe and is likely to be found in the interior of neutron stars. We investigate the possibility that it is formed in the collisions of relativistic heavy nuclei where it can be studied in a controlled and systematic way. As the primary cosmic ray beam provides us with heavy nuclei exceeding 106GeV primary energy, cosmic ray experiments can possibly provide us with a first glimpse of quark-gluon plasma, a state of matter that was the main contributor to the energy of the Universe up to 105s after the Big Bang.