Quantum technologies use entanglement to outperform classical technologies, and often employ strong cooling and isolation to protect entangled entities from decoherence by random interactions. Here we show that the opposite strategy-promoting random interactions-can help generate and preserve entanglement. We use optical quantum non-demolition measurement to produce entanglement in a hot alkali vapor, in a regime dominated by random spin-exchange collisions. We use Bayesian statistics and spin-squeezing inequalities to show that at least 1.52(4)x10(13) of the 5.32(12)x10(13) participating atoms enter into singlet-type entangled states, which persist for tens of spin-thermalization times and span thousands of times the nearest-neighbor distance. The results show that high temperatures and strong random interactions need not destroy many-body quantum coherence, that collective measurement can produce very complex entangled states, and that the hot, strongly-interacting media now in use for extreme atomic sensing are well suited for sensing beyond the standard quantum limit.