In a strong magnetic field, ultra-relativistic electrons or positrons undergo spin flip transitions as they radiate, preferentially spin polarizing in one direction -- the Sokolov-Ternov effect. Here we show that this effect could occur very rapidly (in less than 10 fs) in high intensity ($Igtrsim10^{23}$ W/cm$^{2}$) laser-matter interactions, resulting in a high degree of electron spin polarization (70%-90%).