  We analytically solve the {\it Non-Markovian} single electron spin dynamics
due to hyperfine interaction with surrounding nuclei in a quantum dot. We use
the equation-of-motion method assisted with a large field expansion, and find
that virtual nuclear spin flip-flops mediated by the electron contribute
significantly to a complete decoherence of transverse electron spin correlation
function. Our results show that a 90% nuclear polarization can enhance the
electron spin $T_2$ time by almost two orders of magnitude. In the long time
limit, the electron spin correlation function has a non-exponential $1/t^2$
decay in the presence of both polarized and unpolarized nuclei.
