Generalizing the notion of Newton polytope, we define the Newton-Okounkov body, respectively, for semigroups of integral points, graded algebras and linear series on varieties. We prove that any semigroup in the lattice ℤn is asymptotically approximated by the semigroup of all the points in a sublattice and lying in a convex cone. Applying this we obtain several results. We show that for a large class of graded algebras, the Hilbert functions have polynomial growth and their growth coefficients satisfy a Brunn-Minkowski type inequality. We prove analogues of the Fujita approximation theorem for semigroups of integral points and graded algebras, which imply a generalization of this theorem for arbitrary linear series. Applications to intersection theory include a far-reaching generalization of the Kushnirenko theorem (from Newton polytope theory) and a new version of the Hodge inequality. We also give elementary proofs of the Alexandrov-Fenchel inequality in convex geometry and its analogue in algebraic geometry.