El 1979 fou elegit regidor de l'ajuntament de Madrid, encarregant-se de la regidoria d'Hisenda en la corporació presidida per Enrique Tierno Galván. El desembre d'aquell any, Joaquín Leguina fou elegit secretari general de la Federació Socialista Madrilenya. En el congrés, els antics "convergents", amb suport de l'aparell central del PSOE, en mans de Felipe González, van prendre el poder,[2] desbancant la facció encapçalada per Alonso Puerta (que posteriorment abandonaria el PSOE per a ingressar al Partido de Acción Socialista, un dels fundadors d'Izquierda Unida).
A les eleccions generals d'octubre de 1982, va ser escollit diputat per la província de Madrid, encara que va abandonar l'escó a l'any següent quan, com a cap de llista del PSOE a la Comunitat de Madrid, va ser-ne elegit president. Va ser el primer president de la institució, càrrec que va ocupar entre 1983 i 1995, quan va ser derrotat per Alberto Ruiz Gallardón. Durant els anys noranta, la Federació Socialista Madrilenya va travessar una etapa turbulenta. Leguina, líder dels anomenats "renovadors" (oposats als "guerristes"), va ocupar la secretaria general fins a 1991. En aquest any, va donar el relleu a Teófilo Serrano al qui substituí el 1994, el també renovador i home de confiança de Leguina Jaime Lissavetzky (que es mantindria al capdavant de la FSM fins a 2001).
A les eleccions generals espanyoles de 1996, Leguina va ser elegit diputat, sent reelegit en la següent legislatura (2000-2004), en la qual va ser nomenat president de la Comissió de Defensa del Congrés. Va donar suport Joaquín Almunia en les primàries socialistes per a escollir candidat a la presidència del govern el 1998 (que van ser guanyades per Josep Borrell), i aquest mateix any es va postular com a candidat del PSOE a l'ajuntament de Madrid, però fou derrotat a les primàries per Fernando Morán. Després de la dimissió de Joaquín Almunia com a secretari general del PSOE, Leguina va donar suport a José Bono en el XXXV Congrés del PSOE, el qual va ser derrotat pel després president del Govern, José Luis Rodríguez Zapatero.