This Letter studies the decoherence in a system of two antiferromagnetically coupled spins that interact with a spin bath environment. Systems are considered that range from the rotationally invariant to highly anisotropic spin models, have different topologies and values of parameters that are fixed or are allowed to fluctuate randomly. We explore the conditions under which the two-spin system clearly shows an evolution from the initial spin-up - spin-down state towards the maximally entangled singlet state. We demonstrate that frustration and, especially, glassiness of the spin environment strongly enhances the decoherence of the two-spin system.