Strongly interacting matter as described by the thermodynamics of QCD undergoes a phase transition, from a low temperature hadronic medium to a high temperature quark-gluon plasma state. In the early universe this transition occurred during the early microsecond era. It can be investigated in the laboratory, in collisions of nuclei at relativistic energy, which create "fireballs" of sufficient energy density to cross the QCD Phase boundary. We describe 3 decades of work at CERN, devoted to the study of the QCD plasma and the phase transition. From modest beginnings at the SPS, ultra-relativistic heavy ion physics has evolved today into a central pillar of contemporary nuclear physics and forms a significant part of the LHC program.Strongly ...