Utworzony lewicowy blok ten wygrał wybory parlamentarne w tym samym roku, pozostając jednak w opozycji do nowo powołanego rządu Rolandasa Paksasa.
W styczniu 2001 Algirdas Brazauskas stanął na czele Litewskiej Partii Socjaldemokratycznej, do której formalnie przyłączyła się LDDP. W lipcu tegoż roku został premierem Litwy, gdy po rozpadzie koalicji partii liberalnych, jego ugrupowanie porozumiało się z Nowym Związkiem.
Po wyborach parlamentarnych w 2004 pozostał na tym stanowisku, inicjując nową koalicję rządową z udziałem m.in. Partii Pracy. Urząd premiera sprawował do czerwca 2006. Podał się do dymisji po ujawnieniu szeregu afer w zapleczu politycznym jego rządu, które doprowadziły m.in. do wyjścia z koalicji Partii Pracy. W 2007 zrezygnował także z kierowania socjaldemokratami.
26 czerwca 2010 zmarł w Wilnie w wieku 77 lat na raka prostaty. Metropolita wileński Audrys Bačkis nie zgodził się na wniesienie trumny z ciałem prezydenta do katedry wileńskiej na czas uroczystości pogrzebowych, co wywołało liczne kontrowersje. 1 lipca został pochowany na cmentarzu na Antokolu.
Życie prywatne Jego pierwszą żoną była Julija Brazauskienė, miał z nią córki Audronė i Laimę. Po raz drugi żonaty z Kristiną Butrimienė.