The 4D rotating black hole described by the Kerr geometry possesses many of what was called by Chandrasekhar "miraculous" properties. Most of them are related to the existence of a fundamental hidden symmetry of a principal conformal Killing-Yano (PCKY) tensor. In my talk I shall demonstrate that hidden symmetry of the PCKY tensor plays exceptional role also in higher dimensions. Namely, I shall present the most general spacetime admitting the PCKY tensor and show that is possesses the following properties: 1) It is of the algebraic type D and admits the Kerr-Schild form 2) It allows a separation of variables for the Hamilton-Jacobi, Klein-Gordon, Dirac, and stationary string equations. 3) When the Einstein equations with the cosmological constant are imposed the metric describes the most general known (spherical) Kerr-NUT-AdS black hole spacetime. I will also discuss the generalization of Killing-Yano symmetries for spacetimes with natural "torsion 3-form", such as the black hole of D=5 minimal supergravity, or the Kerr-Sen solution of heterotic string theory, and comment on connection to special Riemannian manifolds admiting Killing spinors.