Laser-ultrasonics is a non-destructive and non-contact technique to generate and detect ultrasound in materials. The measured ultrasonic velocity depends on the orientation distribution of the crystallites and may be used to infer the lowest order texture coefficients. Recrystallization generally involves texture changes and can thus be monitored using ultrasonics. In this paper, cold-rolled samples of an Al-Mg alloy (AA5754) and an Al-Si-Mg-Cu alloy (AA6111) are annealed in a Gleeble thermomechanical simulator at various temperatures. The recrystallization kinetics is monitored in-situ and in real time by laser-ultrasonics. It is found that longitudinal and shear velocity variations correlate well with the recrystallized fraction, as evaluated by metallography and by the softening behavior of samples submitted to similar thermal cycles. It is also found that the ultrasonic behavior is consistent with the randomization of texture and a reduction of the W-400 and W-420 texture coefficients.