We compute the on-shell Euclidean action of Schwarzschild-de Sitter black holes, and take their contributions in the gravitational path integral into account using the formalism of constrained instantons. Although Euclidean de Sitter black hole geometries have conical singularities for generic masses, their on-shell action is finite and is shown to be independent of the Euclidean time periodicity and equal to minus the sum of the black hole and cosmological horizon entropy. We apply this result to compute the probability for a nonrotating, neutral arbitrary mass black hole to nucleate spontaneously in empty de Sitter space, which separates into a constant and a "non-perturbative" contribution, the latter corresponding to the proper saddle-point instanton in the Nariai limit. We also speculate on some further applications of our results, most notably as potential non-perturbative corrections to correlators in the de Sitter vacuum.