Tropical geometry and the theory of Newton-Okounkov bodies are two methods which produce toric degenerations of an irreducible complex projective variety. Kaveh-Manon showed that the two are related. We give geometric maps between the Newton-Okounkov bodies corresponding to two adjacent maximal-dimensional prime cones in the tropicalization of $X$. Under a technical condition, we produce a natural "algebraic wall-crossing" map on the underlying value semigroups (of the corresponding valuations). In the case of the tropical Grassmannian $Gr(2,m)$, we prove that the algebraic wall-crossing map is the restriction of a geometric map. In an Appendix by Nathan Ilten, he explains how the geometric wall-crossing phenomenon can also be derived from the perspective of complexity-one $T$-varieties; Ilten also explains the connection to the "combinatorial mutations" studied by Akhtar-Coates-Galkin-Kasprzyk.