Employing spin-, time-, and energy-resolved photoemission spectroscopy, we present the first study on the spin polarization of a single electronic state after ultrafast optical excitation. Our investigation concentrates on the majority-spin component of the d-band-derived Gd(0001) surface state d↑_z2. While its binding energy shows a rapid Stoner-like shift by 90 meV with an exponential time constant of τ_E=0.6±0.1 ps, the d↑_z2 spin polarization remains nearly constant within the first picoseconds and decays with τ_S=15±8 ps. This behavior is in clear contrast to the equilibrium phase transition, where the spin polarization vanishes at the Curie temperature.