The Newton-Okounkov bodies of linear series on an n-dimensional projective variety is a compact convex body in real n-space which carries information about the linear series. However, in general it is hard to determine in practice. We show that under certain conditions there exist simple "building blocks" for al Newton-Okounkov bodies of a given variety, a so called Minkowski basis. Additionally, we establish a consequence of the existence of a Mikowski basis for the shape of the global Okounkov body studied by Lazarsfeld and Mustata.