We recently showed that if a massive (or charged) body is put in a quantum spatial superposition, the mere presence of a black hole in its vicinity will eventually decohere the superposition. In this paper we show that, more generally, decoherence of stationary superpositions will occur in any spacetime with a Killing horizon. This occurs because, in effect, the long-range field of the body is registered on the Killing horizon which, we show, necessitates a flux of "soft horizon gravitons/photons" through the horizon. The Killing horizon thereby harvests "which path" information of quantum superpositions and will decohere any quantum superposition in a finite time. It is particularly instructive to analyze the case of a uniformly accelerating body in a quantum superposition in flat spacetime. As we show, from the Rindler perspective the superposition is decohered by "soft gravitons/photons" that propagate through the Rindler horizon with negligible (Rindler) energy. We show that this decoherence effect is distinct from--and larger than--the decoherence resulting from the presence of Unruh radiation. We further show that from the inertial perspective, the decoherence is due to the radiation of high frequency (inertial) gravitons/photons to null infinity. (The notion of gravitons/photons that propagate through the Rindler horizon is the same notion as that of gravitons/photons that propagate to null infinity.) We also analyze the decoherence of a spatial superposition due to the presence of a cosmological horizon in de Sitter spacetime. We provide estimates of the decoherence time for such quantum superpositions in both the Rindler and cosmological cases. Although we explicitly treat the case of spacetime dimension $d=4$, our analysis applies to any dimension $d \geq 4$.

16 pages, 1 figure. Accepted for publication in Phys. Rev. D. v2: Added clarifying remarks and a figure, and pointed out that the effect arises for any d>=4; corrected equation (3.18)