We compare the laser-driven demagnetization dynamics of the rare earths gadolinium and terbium by mapping their transient valance band structures with time- and angle-resolved photoelectron spectroscopy. In both metals, the minority and majority spin valence bands evolve independently with different time constants after optical excitation. The ultrafast shift of the partially unoccupied minority spin bulk band to higher binding energy and of the majority spin surface state to lower binding energy suggests spin transport between surface and bulk. The slower response of the fully occupied majority spin band follows the lattice temperature and is attributed to Elliott-Yafet type spin-flip scattering. Terbium shows a stronger and faster decay of the exchange splitting, pointing to ultrafast magnon emission via 4f spin-to- lattice coupling.