Spin-changing atomic collisions are important for thermally robust entanglement generation with applications in quantum information. Here the authors demonstrate record high spin state correlations and long spin relaxation times in the collision of two Rb atoms at relatively warm temperatures.