We use time-resolved x-ray diffraction and magneto-optical Kerr effect to study the laser-induced antiferromagnetic to ferromagnetic phase transition in FeRh. The structural response is given by the nucleation of independent ferromagnetic domains (tau(1) similar to 30 ps). This is significantly faster than the magnetic response (tau(2) similar to 60 ps) given by the subsequent domain realignment. X-ray diffraction shows that the two phases coexist on short time scales and that the phase transition is limited by the speed of sound. A nucleation model describing both the structural and magnetic dynamics is presented.