We report evidence for an anti-correlation between spin temperature $T_s$ and metallicity [Z/H], detected at $3.6 sigma$ significance in a sample of 26 damped Lyman-$alpha$ absorbers (DLAs) at redshifts $0.09 < z < 3.45$. The anti-correlation is detected at $3 sigma$ significance in a sub-sample of 20 DLAs with measured covering factors, implying that it does not stem from low covering factors. We obtain $T_s = (-0.68 pm 0.17) times {rm [Z/H]} + (2.13 pm 0.21)$ from a linear regression analysis. Our results indicate that the high $T_s$ values found in DLAs do not arise from differences between the optical and radio sightlines, but are likely to reflect the underlying gas temperature distribution. The trend between $T_s$ and [Z/H] can be explained by the larger number of radiation pathways for gas cooling in galaxies with high metal abundances, resulting in a high cold gas fraction, and hence, a low spin temperature. Conversely, low-metallicity galaxies have fewer cooling routes, yielding a larger warm gas fraction and a high $T_s$. Most DLAs at $z>1.7$ have low metallicities, [Z/H] $< -1$, implying that the HI in high-$z$ DLAs is predominantly warm. The anti-correlation between $T_s$ and [Z/H] is consistent with the presence of a mass-metallicity relation in DLAs, suggested by the tight correlation between DLA metallicity and the kinematic widths of metal lines. Most high-$z$ DLAs are likely to arise in galaxies with low masses ($M_{rm vir} < 10^{10.5} M_odot$), low metallicities ([Z/H]$< -1$, and low cold gas fractions.