We wrześniu tego samego roku założył własną partię Kongres Nepalski (Demokratyczny)NEPALI CONGRESS AN INTRODUCTION, Nepali Congress Party..
Z urzędu szefa rządu Deuba został usunięty na skutek bezkrwawego zamachu stanu przeprowadzonego przez króla Gyanendrę 4 października 2002"Nepal King, Urging Elections, Dismisses Premier and Takes Power", The New York Times, 5 października 2002..
Gyanendra przywrócił go na stanowisko 3 czerwca 2004 po politycznych protestach, upadku dwóch kolejnych rządów i braku odpowiedniego kandydata na stanowisko premiera. W swoim trzecim gabinecie Deuba objął również funkcję ministra spraw zagranicznych i obrony"World Briefing | Asia: Nepal: King Reappoints Premier He Fired", The New Yrok Times, 3 czerwca 2001..
1 lutego 2005 król Gyanendra rozwiązał rząd i parlament i przejął na ponad rok całkowitą władzę w państwie"Former Nepal PM freed from jail", BBC News, 14 lutego 2006.. Deuba został skazany na dwa lata więzienia w lipcu 2005 pod zarzutem korupcji. 13 lutego 2006 został zwolniony z odbywania kary i oczyszczony z zarzutów.