After excitation by femtosecond laser pulses, Gd and Tb exhibit ultrafast demagnetization in two steps, with the time constant of the second step linked to the coupling strength of the 4f magnetic moments to the lattice. In time-resolved magneto-optical Kerr effect measurements of Gd1−xTbx alloys, we observe a decrease in this time constant from 33 to 9 ps with Tb content x increasing from 0 to 0.7. We explain this behavior by the stronger spin-lattice coupling of Tb compared to Gd, which increases the effective spin-lattice coupling in Gd1−xTbx with x. In contrast, the faster time constant of the first demagnetization step exhibits no dependence on x. Additional time- and element-resolved x-ray magnetic circular dichroism measurements show a two-step demagnetization of Gd and Tb in Gd0.6Tb0.4 with an equivalent time scale of the second step but a different magnitude of demagnetization which persists for 15 ps. We explain this by an increased coupling of the Gd 4f magnetic moments to the lattice compared to pure Gd, via interatomic exchange coupling to the neighboring Tb 4f moments mediated by 5d electrons, which has limited efficiency and allows an estimation of a characteristic time scale of the interatomic exchange coupling. We assign the first demagnetization step to the dynamics of the laser-excited 5d electrons, while the second demagnetization step is dominated by the strength of spin-lattice coupling of the 4f electrons.