We explore the spacetime structure near nonextremal horizons in any spacetime dimension greater than two and discover a wealth of novel results: (i) Different boundary conditions are specified by a functional of the dynamical variables, describing inequivalent interactions at the horizon with a thermal bath. (ii) The near horizon algebra of a set of boundary conditions, labeled by a parameter s, is given by the semidirect sum of diffeomorphisms at the horizon with "spin-s supertranslations." For s=1 we obtain the first explicit near horizon realization of the Bondi-Metzner-Sachs algebra. (iii) For another choice, we find a nonlinear extension of the Heisenberg algebra, generalizing recent results in three spacetime dimensions. This algebra allows us to recover the aforementioned (linear) ones as composites. (iv) These examples allow us to equip not only black holes, but also cosmological horizons with soft hair. We also discuss implications of soft hair for black hole thermodynamics and entropy.