We study spin relaxation and decoherence in a GaAs quantum dot due to spin-orbit (SO) interaction. We derive an effective Hamiltonian which couples the electron spin to phonons or any other fluctuation of the dot potential. We show that the spin decoherence time is as large as the spin relaxation time , under realistic conditions. For the Dresselhaus and Rashba SO couplings, we find that, in leading order, the effective field can have only fluctuations transverse to the applied field. As a result, for arbitrarily large Zeeman splittings, in contrast to the naively expected case . We show that the spin decay is drastically suppressed for certain -field directions and ratios of SO coupling constants. Finally, for the spin-phonon coupling, we show that for all SO mechanisms in leading order in the electron-phonon interaction.