Based on the work of Okounkov (\cite{Ok96}, \cite{Ok03}), Lazarsfeld and
Musta\c t\u a (\cite{LM08}) and Kaveh and Khovanskii (\cite{KK08}) have
independently associated a convex body, called the Okounkov body, to a big
divisor on a smooth projective variety with respect to a complete flag. In this
paper we consider the following question: what can be said about the set of
convex bodies that appear as Okounkov bodies? We show first that the set of
convex bodies appearing as Okounkov bodies of big line bundles on smooth
projective varieties with respect to admissible flags is countable. We then
give a complete characterisation of the set of convex bodies that arise as
Okounkov bodies of $\R$-divisors on smooth projective surfaces. Such Okounkov
bodies are always polygons, satisfying certain combinatorial criteria. Finally,
we construct two examples of non-polyhedral Okounkov bodies. In the first one,
the variety we deal with is Fano and the line bundle is ample. In the second
one, we find a Mori dream space variety such that under small perturbations of
the flag the Okounkov body remains non-polyhedral.