We prove that non-extremal black holes in four-dimensional general relativity exhibit an infinite-dimensional symmetry in their near horizon region. By prescribing a physically sensible set of boundary conditions at the horizon, we derive the algebra of asymptotic Killing vectors, which is shown to be infinite-dimensional and includes, in particular, two sets of supertranslations and two mutually commuting copies of the Witt algebra. We define the surface charges associated to the asymptotic diffeomorphisms that preserve the boundary conditions and discuss the subtleties of this definition, such as the integrability conditions and the correct definition of the Dirac brackets. When evaluated on the stationary solutions, the only non-vanishing charges are the zero-modes. One of them reproduces the Bekenstein-Hawking entropy of Kerr black holes. We also study the extremal limit, recovering the NHEK geometry. In this singular case, where the algebra of charges and the integrability conditions get modified, we find that the computation of the zero-modes correctly reproduces the black hole entropy. Furthermore, we analyze the case of three spacetime dimensions, in which the integrability conditions notably simplify and the field equations can be solved analytically to produce a family of exact solutions that realize the boundary conditions explicitly. We examine other features, such as the form of the algebra in the extremal limit and the relation to other works in the literature.