We discuss the effect of gravitational interactions on the lifetime of the Higgs vacuum where generic quantum gravity corrections are taken into account. We show how 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 constraints on parameter space of corrections to the Higgs potential are outlined, and implications for collider black holes discussed.