Od 19 listopada 1992 do 11 grudnia 1996 sprawował urząd ministra spraw zagranicznych w rządzie, na czele którego stał Nicolae Văcăroiu. W 1996 po raz pierwszy został wybrany w skład Senatu. Początkowo był związany z Partią Socjaldemokracji w Rumunii, w 1997 współtworzył i stanął na czele Sojuszu na rzecz Rumunii. Ugrupowanie to w 2000 nie dostało się do parlamentu, a w 2002 wraz ze swoim liderem dołączyło do Partii Narodowo-Liberalnej. W międzyczasie w 2000 Teodor Meleșcanu wystartował w wyborach prezydenckich, uzyskując niespełna 2% głosów. Po dołączeniu do PNL od 2002 do 2010 pełnił funkcję wiceprzewodniczącego tej partii, w 2002 rozpoczął również prowadzenie prywatnej praktyki adwokackiej.
W 2004 ponownie został wybrany do Senatu. Od 5 kwietnia 2007 do 22 grudnia 2008 był ministrem obrony narodowej w gabinecie Călina Popescu-Tăriceanu, od 15 stycznia 2008 do 29 lutego 2008 pełnił także obowiązki ministra sprawiedliwości. W 2008 po raz trzeci został senatorem, rezygnując z mandatu w 2012, tj. na kilka miesięcy przed końcem kadencji. W lutym tego samego roku z nominacji prezydenta Traiana Băsescu objął stanowisko szefa Służby Wywiadu Zagranicznego, które zajmował do września 2014. Przyjmując tę propozycję od skonfliktowanego z PNL prezydenta, zawiesił swoje członkostwo w partii, następnie został z niej usunięty.