We show that the present-day dark matter abundance can be produced through a novel mechanism that involves a very rapid thermal freeze-out caused by inhomogeneous heating and successive fast cooling of small fireballs in the early Universe. The fireballs can be produced from energy deposited in small scale structure growth induced by Yukawa interactions in certain particle species. Yukawa interactions are known to cause growth of halos even during a radiation dominated era, and the same interactions facilitate cooling and collapse of the halos by the emission of scalars. Energy deposited in the Standard Model plasma at the locations of the halo collapse can heat the plasma, re-establishing thermal equilibrium. The subsequent expansion and cooling of plasma fireballs leads to freeze-out of dark matter on timescales much shorter than the Hubble time. This mechanism can produce the right abundance of dark matter for masses and annihilation cross sections previously thought to be ruled out.