  An edge coloring of the $n$-vertex complete graph, $K_n$, is a Gallai
coloring if it does not contain any rainbow triangle, that is, a triangle whose
edges are colored with three distinct colors. We prove that for $n$ large and
every $k$ with $k\le 2^{n/4300}$, the number of Gallai colorings of $K_n$ that
use at most $k$ given colors is $(\binom{k}{2}+o_n(1))\,2^{\binom{n}{2}}$. Our
result is asymptotically best possible and implies that, for those $k$, almost
all Gallai $k$-colorings use only two colors. However, this is not true for $k
\ge \Omega (2^{2n})$.
