High energy nuclear collisions produce far-from-equilibrium matter with a high density of gluons at early times. We identify for the first time two local order parameters for condensation, which can occur as a consequence of the large density of gluons. We demonstrate that an initial over-occupation of gluons can lead to the formation of a macroscopic zero mode towards low momenta that scales proportionally with the volume of the system—this defines a gauge invariant condensate. The formation of a condensate at early times has intriguing implications for early time dynamics in heavy ion collisions.