Il fait son retour au Parlement à l'occasion des élections de [4]. Il est ensuite réélu en et en [5],[6]. Lors de ce dernier scrutin, le Parti populaire socialiste recule nettement et Gert Petersen en quitte la présidence qu'il occupait depuis 1974. Nielsen remporte contre Steen Gade l'élection pour lui succéder en 1991.
Il devient l'une des figures du "non" qui remporte une victoire surprise lors du référendum de sur la ratification par le Danemark du traité de Maastricht. Le , il annonce son soutien à l'accord d'Édimbourg qui permet au Danemark de ratifier le traité, en échange de quatre options de retrait. Sa position suscite alors la controverse au sein de son parti, bien que l'accord soit accepté par référendum le [7].
Il est réélu au Folketing lors des élections législatives de [13]. En , il annonce qu'il ne sera pas candidat à sa réélection lors du prochain scrutin, après plus de trente ans au Folketing[14].