Nyrup Rasmussen werd in een arbeidersgezin in Esbjerg geboren. In 1971 studeerde hij als econoom af aan de Universiteit van Kopenhagen. Van 1971 tot en met 1988 vervulde hij diverse functies bij Deense instellingen, onder meer bij de overkoepelende Deense vakbondsvereniging LO. In 1987 werd hij vice-fractievoorzitter van de Sociaaldemocratische partij en een jaar later werd hij voor het eerst verkozen als lid van het Folketing (het Deense parlement). In 1992 werd hij fractievoorzitter.
Na het vroegtijdige aftreden van premier Poul Schlüter in januari 1993 werd Rasmussen naar voren geschoven als de nieuwe premier van Denemarken. Hij leidde zijn partij in de jaren nadien naar overwinningen bij de parlementsverkiezingen van 1994 en die van 1998 en stond aan het hoofd van vier opeenvolgende kabinetten, waarin hij in verschillende samenstellingen (maar altijd samen met Radikale Venstre) regeerde.
Het einde van Rasmussens premierschap werd overschaduwd door het verlies van het referendum over de invoering van de euro in september 2000. Een meerderheid van de Denen wees de Europese munt hierbij af. Bij de parlementsverkiezingen van 2001 leed Rasmussen vervolgens een gevoelige nederlaag tegen Anders Fogh Rasmussen van de liberale partij Venstre en zagen de sociaaldemocraten hun status als grootste partij van Denemarken voor het eerst sinds 1920 sneuvelen. Rasmussen moest zijn premierschap afstaan en trad in december 2002 ook af als partijleider. Hij bleef wel nog tot 2004 oppositie voeren in het Deense parlement.