W 1986 po raz pierwszy uzyskał mandat posła do Kongresu Deputowanych III kadencji. Do niższej izby Kortezów Generalnych był następnie wybierany w wyborach w 1989, 1993, 1996, 2000, 2004 i 2008. Awansował jednocześnie w strukturze partyjnej, obejmując w 1988 przywództwo w PSOE w prowincji León. W 1997 dołączył do federalnego komitetu wykonawczego partii.
22 lipca 2000, po drugiej z rzędu porażce wyborczej socjalistów i rezygnacji złożonej przez Joaquína Almunię, został wybrany na nowego sekretarza generalnego Hiszpańskiej Socjalistycznej Partii Robotniczej. Otrzymał poparcie 414 z 993 delegatów, pokonując m.in. swojego głównego konkurenta José Bono Martíneza. 27 października 2002 podczas masowego wiecu ogłoszono go kandydatem PSOE na premiera po wyborach w 2004. Kampanię wyborczą kierowani przez niego socjaliści prowadzili m.in. pod hasłem wyprowadzenia hiszpańskich sił z Iraku. Socjaliści zwyciężyli w tych wyborach, uzyskując 164 mandaty w 350-osobowym Kongresie Deputowanych. Za główną przyczynę ich zwycięstwa uznano zamachy terrorystyczne w Madrycie, które miały miejsce na trzy dni przed głosowaniem.