By comparing femtosecond laser-pulse-induced spin dynamics in the surface state of the rare earth metals Gd and Tb, we show that the spin polarization of valence states in both materials decays with significantly different time constants of 15 ps and 400 fs, respectively. The distinct spin polarization dynamics in Gd and Tb are opposed by similar exchange splitting dynamics in the two materials. The different time scales observed in our experiment can be attributed to weak and strong 4f spin to lattice coupling in Gd and Tb, suggesting an intimate coupling of spin polarization and 4f magnetic moment. While in Gd the lattice mainly acts as a heat sink, it contributes significantly to ultrafast demagnetization of Tb. This helps explain why all optical switching is observed in FeGd—but rarely in FeTb-based compounds.