The correspondence between lattice polytopes and divisors on a toric variety is a basic incarnation of a connection that extends far beyond toric varieties. In this talk, we will give a gentle introduction to Newton-Okounkov bodies, which provide a correspondence between convex geometry and divisors on a general variety. While Newton-Okounkov bodies are in generally very far from being polyhedral, we will highlight an important situation in which the Newton-Okounkov body is polyhedral and what consequences this has for the geometry of the associated variety.