The bulk-boundary correspondence is among the central issues of non-Hermitian topological states. We show that a previously overlooked "non-Hermitian skin effect" necessitates redefinition of topological invariants in a generalized Brillouin zone. The resultant phase diagrams dramatically differ from the usual Bloch theory. Specifically, we obtain the phase diagram of the non-Hermitian Su-Schrieffer-Heeger model, whose topological zero modes are determined by the non-Bloch winding number instead of the Bloch-Hamiltonian-based topological number. Our work settles the issue of the breakdown of conventional bulk-boundary correspondence and introduces the non-Bloch bulk-boundary correspondence.