A Newton-Okounkov body is a convex set associated to a projective variety, equipped with a valuation. These bodies generalize the theory of Newton polytopes. Work of Kaveh-Manon gives an explicit link between tropical geometry and Newton-Okounkov bodies. We use this link to describe a wall-crossing phenomenon for Newton-Okounkov bodies. As an application we show how the wall-crossing formula for the tropicalization of Gr(2,m) is an instance of our phenomenon for Newton-Okounkov bodies. Joint work with Megumi Harada.