We study the effect of primordial black holes on the classical rate of nucleation of AdS regions within the standard electroweak vacuum at high temperature. We find that the energy barrier for transitions to the new vacuum, which determines the exponential suppression of the nucleation rate, can be reduced significantly, or even eliminated completely, in the black-hole background if the Standard Model Higgs is coupled to gravity through the renormalizable term $\xi {\cal R} h^2$.