W styczniu 1996 Andreas Papandreu ustąpił ze stanowiska premiera. 22 stycznia tegoż roku Kostas Simitis, po uzyskaniu partyjnej nominacji, objął ten urząd. 30 czerwca tegoż roku został również nowym przewodniczącym PASOK-u (Andreas Papandreu kierował partią do czasu swojej śmierci tydzień wcześniej). Socjaliści pod przywództwem Kostasa Simitisa zwyciężali w wyborach w 1996 i 2000. Ich lider po tych wyborach pozostawał premierem, tworząc dwa kolejne gabinety. Na czele greckiego rządu stał do 10 marca 2004, gdy po przegranych przez PASOK wyborach nowym premierem został Kostas Karamanlis z Nowej Demokraci. Miesiąc wcześniej na czele partii zastąpił go Jorgos Papandreu.
Był później członkiem Komitetu Działania na rzecz Europejskiej Demokracji, który przygotował założenia do nowego traktatu dla Unii Europejskiej. W 2008 na tle kwestii ratyfikacji traktatu lizbońskiego doszło do wewnątrzpartyjnego sporu między nim a Jorgosem Papandreu.