Regeringen gik undervejs fra 4 til 2 partier, efter [[Kristeligt Folkeparti]] røg ud af [[Folketinget]] ved valget [[1994]] og [[Centrum-Demokraterne]] forlod regeringen i [[1996]]. Regeringen fik klart genvalg i [[1994]], men i [[1998]] blev det et tæt valg, hvor Nyrup først kunne erklære sig som vinder efter stemmerne på [[Færøerne]] blev talt op.
Selvom der var fremgang i [[Danmark]], havde Nyrup det svært i medierne. Han blev kaldt "uld i mund", fordi han ikke altid udtalte sig somså folk kunne forstå det, og i [[1995]] ville han cykle for at demonstrere mod franske atomprøvesprængninger, men blev kendt for at have en alt for lille cykelhjelm på, billeder der klæbede til ham. I [[1998]] valgkampen lovede han ikke at røre efterlønnen, men den blev alligevel ændret samme år. Det nye parti, [[Dansk Folkeparti]] voksede på det tidspunkt frem med at ville dæmme op for indvandringen, og med en [[islam]]-kritisk profil. Nyrup syntes ikke om deres holdninger og tone i debatten, og kaldte dem "ikke-stuerene" fra Folketingets talerstol. I [[2001]] tabte han valget stort til [[Anders Fogh Rasmussen]], efter en valgkamp hvor indvandring var et af de store emner i debatten. Nyrup fortsatte som partiformand i oppostitionen, og forsøgte at nyskabe partiet ved at skifte næstformænd og partisekretær ud, og skifte partinavn fra Socialdemokratiet til [[Socialdemokraterne]]. Men efter kun et år valgte han i efteråret [[2002]] at gå af og overlade pladsen til [[Mogens Lykketoft]].
