We present a quantum solution to the electron spin decoherence by a nuclear pair-correlation method for the electron-nuclear spin dynamics under a strong magnetic field and a temperature high for the nuclear spins but low for the electron. The theory incorporates the hyperfine interaction, the intrinsic (both direct and indirect) nuclear interactions, and the extrinsic nuclear coupling mediated by the hyperfine interaction with the single electron in question. The last is shown to be important in free-induction decay (FID) of the single electron spin coherence. The spin echo eliminates the hyperfine-mediated decoherence but only reduces the decoherence by the intrinsic nuclear interactions. Thus, the decoherence times for single spin FID and ensemble spin echo are significantly different. The decoherence is explained in terms of quantum entanglement, which involves more than the spectral diffusion. ; Comment: Expanded version. While the main body of the manuscript presents a self-contained story, we have prepared Appendices for readers who are interested in further details of our theory. Phys. Rev. B. (2006) in press