We study the time evolution of a single spin coupled inhomogeneously to a spin environment. Such a system is realized by a single electron spin bound in a semiconductor nanostructure and interacting with surrounding nuclear spins. We find striking dependencies on the type of initial state of the nuclear spin system. Simple product states show a profoundly different behavior than randomly correlated states whose time evolution provides an illustrative example of quantum parallelism and entanglement in a decoherence phenomenon.