  Given a finitely generated algebra $A$, it is a fundamental question whether
$A$ has a full rank discrete (Krull) valuation $\mathfrak{v}$ with finitely
generated value semigroup. We give a necessary and sufficient condition for
this, in terms of tropical geometry of $A$. In the course of this we introduce
the notion of a Khovanskii basis for $(A, \mathfrak{v})$ which provides a
framework for far extending Gr\"obner theory on polynomial algebras to general
finitely generated algebras. In particular, this makes a direct connection
between the theory of Newton-Okounkov bodies and tropical geometry, and toric
degenerations arising in both contexts. We also construct an associated
compactification of $Spec(A)$. Our approach includes many familiar examples
such as the Gel'fand-Zetlin degenerations of coordinate rings of flag varieties
as well as wonderful compactifications of reductive groups. We expect that many
examples coming from cluster algebras naturally fit into our framework.
