W 2000 uzyskał mandat posła do Izby Deputowanych, z którego jednak w tym samym roku zrezygnował.
W 2002 został przewodniczącym liberałów. Przed wyborami prezydenckimi w 2004 doprowadził do sojuszu swojej partii z Partią Demokratyczną Traiana Băsescu. W lutym 2004 został wspólnym kandydatem tych ugrupowań na urząd prezydenta. Zrezygnował ostatecznie z udziału w wyborach oraz z przewodzenia PNL, motywując tę decyzję poważnymi problemami zdrowotnymi. Nowym kandydatem koalicji został Traian Băsescu, który wygrał wybory. Theodor Stolojan od 2004 do 2006 był doradcą prezydenta.
W październiku 2006 został wykluczony z Partii Narodowo-Liberalnej. W grudniu 2006 utworzył własne ugrupowanie, Partię Liberalno-Demokratyczną. W wyborach do Parlamentu Europejskiego w 2007 uzyskał mandat eurodeputowanego z ramienia PLD. W styczniu 2008 doprowadził do połączenia liberalnych demokratów z Partią Demokratyczną w Partię Demokratyczno-Liberalną, której został pierwszym wiceprzewodniczącym.