We present a quantum theory of black hole (and other) horizons, in which the standard assumptions of complementarity are preserved without contradicting information theoretic considerations. After the scrambling time, the quantum mechanical structure of a black hole becomes that of an eternal black hole at the microscopic level. In particular, the stretched horizon degrees of freedom and the states entangled with them can be mapped into the near-horizon modes in the two exterior regions of an eternal black hole, whose mass is taken to be that of the evolving black hole at each moment. Salient features arising from this picture include (i) the number of degrees of freedom needed to describe a black hole is eA/2lP2, where A is the area of the horizon; (ii) black hole states having smooth horizons, however, span only an eA/4lP2-dimensional subspace of the relevant eA/2lP2- dimensional Hilbert space; (iii) internal dynamics of the horizon is such that an infalling observer finds a smooth horizon with a probability of 1 if a state stays in this subspace. We identify the structure of local operators responsible for describing semiclassical physics in the exterior and interior spacetime regions and show that this structure avoids the arguments for firewalls - the horizon can keep being smooth throughout the evolution. We discuss the fate of infalling observers under various circumstances, especially when the observers manipulate degrees of freedom before entering the horizon, and we find that an observer can never see a firewall by making a measurement on early Hawking radiation. We also consider the presented framework from the viewpoint of an infalling reference frame and argue that Minkowski-like vacua are not unique. In particular, the number of true Minkowski vacua is infinite, although the label discriminating these vacua cannot be accessed in usual nongravitational quantum field theory. An application of the framework to de Sitter horizons is also discussed. © 2013 American Physical Society.