Ponownie wybierano go na przewodniczącego UP na trzech kolejnych kongresach. Przed wyborami prezydenckimi w 2000 doprowadził do poparcia przez UP kandydatury Aleksandra Kwaśniewskiego. Podpisał następnie porozumienie z Sojuszem Lewicy Demokratycznej o utworzeniu na potrzeby wyborów parlamentarnych w 2001 koalicji wyborczej Sojusz Lewicy Demokratycznej – Unia Pracy. W wyborach tych koalicja zdobyła ponad 41% poparcia a Unia Pracy 16 mandatów poselskich i 7 senatorskich. Pozwoliło jej to stworzyć na początku kadencji samodzielny klub poselski.
Wybrano go wówczas po raz trzeci na posła z okręgu konińskiego, uzyskał 42 546 głosów. 6 października 2001 objął urząd wicepremiera i ministra infrastruktury w rządzie Leszka Millera, zajmując te stanowiska do 2 maja 2004. W 2003 doprowadził do uchwalenia tzw. specustawy drogowej, zakładającej uproszczenie procesu pozyskiwania gruntów pod budowę dróg. W 2004 doprowadził do utworzenia Krajowego Funduszu Drogowego oraz do wprowadzenia (po odrzuceniu przez Sejm projektu opłat winietowych) obligatoryjnej opłaty paliwowej, stanowiącej źródło środków krajowych na budowę i remonty dróg. Kierował negocjacjami akcesyjnymi Polski do Unii Europejskiej w kilku obszarach negocjacyjnych.