We develop the topological band theory for systems described by non-Hermitian Hamiltonians, whose energy spectra are generally complex. After generalizing the notion of gapped band structures to the non-Hermitian case, we classify "gapped" bands in one and two dimensions by explicitly finding their topological invariants. We find nontrivial generalizations of the Chern number in two dimensions, and a new classification in one dimension, whose topology is determined by the energy dispersion rather than the energy eigenstates. We then study the bulk-edge correspondence and the topological phase transition in two dimensions. Different from the Hermitian case, the transition generically involves an extended intermediate phase with complex-energy band degeneracies at isolated "exceptional points" in momentum space. We also systematically classify all types of band degeneracies.