The theory of Newton-Okounkov bodies is a generalization of that of Newton polytopes for toric varieties, and gives a general framework to associate convex bodies with algebraic varieties. In this talk, I prove that the Newton-Okounkov body of a Schubert variety with respect to a specific valuation is identical to the polyhedral realization of a Demazure crystal, and also explain that Kashiwara's involution (*-operation) on crystal bases corresponds to a change of valuations on the function field (Newton-Okounkov bodies depend heavily on a choice of valuations).