La 3-an de marto2000 li devis demisii kaj transdoni sian postenon al la politikisto Jens Stoltenberg de la socialdemokratia Laborista Partio (Arbeiderpartiet), post kiam li en la parlamento perdis fidan voĉdonon en konflikto pri la norvegia energia ekonomio.
Post kiam la Laborista Partio dum la sekvaj parlamentaj balotoj de la jaro 2001 amplekse perdis voĉojn, la norvega reĝo Harald la 19-an de oktobro2001 denove nomumis lin ĉefministro. Li gvidis malplimultan registaron en koalicio de la konservativuloj, la liberala Venstre-partio kaj lia propra Kristana Popola Partio.