It has been argued that, while the individual terms in the generalized entropy, Sgen=A/4GN+Sext, are ill-defined in the semiclassical limit, their sum is well-defined if one takes into account perturbative quantum gravitational effects. The first term diverges as GN→0, and the second diverges due to the infinite entanglement across the horizon which is characteristic of type III von Neumann algebras. It was recently shown that the von Neumann algebra of observables “gravitationally dressed” to the mass of a Schwarzschild-AdS black hole or the energy of an observer in de Sitter spacetime admit a well-defined trace. The algebras are type II∞ (which does not admit a maximum entropy state) and type II1 (which admits a maximum entropy state) respectively, and the von Neumann entropy of “semiclassical” states was found to be (up to an additive constant) the generalized entropy. However, these arguments rely on the existence of a stationary “equilibrium (KMS) state” and do not apply to, for example, black holes formed from gravitational collapse, Kerr black holes, or black holes in asymptotically de Sitter spacetime. These spacetimes are stationary but not in thermal equilibrium. In this paper, we present a general framework for obtaining the algebra of “gravitationally dressed” observables for a linear, Klein-Gordon field on any spacetime with a (bifurcate) Killing horizon. We prove, assuming the existence of a stationary state—which is not necessarily KMS—and suitable asymptotic decay of solutions, a “structure theorem” that the algebra of “gravitationally dressed” observables always contains a type II factor of observables “localized” on the horizon. These assumptions have been rigorously proven in most cases of interest in this paper. Applying our general framework to the algebra of observables in the exterior of an asymptotically flat Kerr black hole where the fields are dressed to the black hole mass and angular momentum we find that the algebra is the product of a type II∞ algebra on the horizon and a type I∞ algebra at past null infinity. The full algebra is type II∞, and the von Neumann entropy of semiclassical states is the generalized entropy. In the case of Schwarzschild-de Sitter, despite the fact that we must introduce an observer, the algebra of observables dressed to the perturbed areas of the black hole and cosmological horizons is the product of type II∞ algebras on each horizon. The entropy of semiclassical states is given by the sum of the areas of the two horizons as well as the entropy of quantum fields in between the horizons. Our results suggest that in all cases where there exists another “boundary structure” (e.g., an asymptotic boundary or another Killing horizon) the algebra of observables is type II∞ and in the absence of such structures (e.g. de Sitter spacetime) the algebra is type II1.