We discuss the effect of gravitational interactions on the lifetime of the Higgs vacuum where generic quantum gravity corrections are taken into account. Using a "thin-wall" approximation, we provide a proof of principle that small black holes can act as seeds for vacuum decay, spontaneously nucleating a new Higgs phase centered on the black hole with a lifetime measured in millions of Planck times rather than billions of years. The corresponding parameter space constraints are, however, extremely stringent; therefore, we also present numerical evidence suggesting that with thick walls, the parameter space may open up. Implications for collider black holes are discussed.