The theory of Newton-Okounkov bodies is a generalization of that of Newton polytopes for toric varieties, and it gives a systematic method of constructing toric degenerations of projective varieties. In this paper, we study Newton-Okounkov bodies of Schubert varieties from the theory of cluster algebras. We construct Newton-Okounkov bodies using specific valuations which generalize extended g-vectors in cluster theory, and discuss how these bodies are related to string polytopes and Nakashima-Zelevinsky polytopes.