We investigate a new mechanism for the cosmological QCD phase transition: inhomogeneous nucleation. The primordial temperature fluctuations, measured to be deltaT/T approximately 10(-5), are larger than the tiny temperature interval in which bubbles would form in the standard picture of homogeneous nucleation. Thus the bubbles nucleate at cold spots. We find the typical distance between bubble centers to be a few meters. This exceeds the estimates from homogeneous nucleation by 2 orders of magnitude. The resulting baryon inhomogeneities may affect primordial nucleosynthesis.