The phase transition from hadronic to quark matter may take place already during the early post-bounce stage of core collapse supernovae when matter is still hot and lepton rich. If the phase transition is of first order and exhibits a barrier, the formation of the new phase occurs via the nucleation of droplets. We investigate the thermal nucleation of a quark phase in supernova matter and calculate its rate for a wide range of physical parameters. We show that the formation of the first droplet of a quark phase might be very fast and therefore the phase transition to quark matter could play an important role in the mechanism and dynamics of supernova explosions.