Abgeordneter und Finanzminister

Kostow begann seine politische Laufbahn erst 1990 nach dem durch den Fall der Berliner Mauer begonnenen Zusammenbruch der kommunistischen Regierung von Todor Schiwkow. Zunächst wurde er Wirtschaftsexperte der 1990 neu gegründeten antikommunistischen Union der demokratischen Kräfte (Sajus na Demokratitschni Sili).

Für die SDS wurde er 1990 erstmals zum Abgeordneten der Nationalversammlung gewählt. Seit 2004 gehört er der Nationalversammlung als Abgeordneter der DSB an.

Am 7. Dezember 1990 wurde er zum Finanzminister in die Regierung von Ministerpräsident Dimitar Popow berufen. Das Amt des Finanzministers übernahm er im Anschluss daran auch in der Regierung von Ministerpräsident Filip Dimitrow vom 8. November 1991 bis zum 30. Dezember 1992.

Parteivorsitzender und Ministerpräsident

Im Dezember 1994 wurde er zum Vorsitzenden der SDS gewählt. Dieses Amt übte er bis zum Juli 2001 aus.

Nach dem Sieg der SDS bei den Wahlen zur Nationalversammlung am 19. April 1997, bei der die SDS 52,3 Prozent der Stimmen und 137 der 240 Parlamentsmandate erhielt, wurde er am 21. Mai 1997 als Nachfolger von Stefan Sofijanski Ministerpräsident.

Seine bis zum 24. Juli 2001 amtierende Regierung war die erste post-kommunistische Regierung, die trotz der angespannten Wirtschaftslage die gesamte vierjährige Wahlzeit im Amt blieb. Während seiner Amtszeit wurde zur Bekämpfung der Inflation ein Währungsrat eingesetzt und die bulgarische Währung an die DM gebunden (1999 an den Euro). Weiter wurden nicht nur lange verzögerte Wirtschaftsreformen wie die Anpassung der Gesetze an die Marktwirtschaft und die Privatisierung von Staatsbetrieben umgesetzt, sondern auch die Gespräche über Beitrittsverhandlungen mit der Europäischen Union begonnen, die am 1. Januar 2007 letztlich zum Beitritt Bulgariens zur Europäischen Union führten.

Der Regierung gelang trotz der für die Wirtschaft Bulgariens äußerst nachteiligen Jugoslawienkrise eine Wende mit der Folge einer politischen und volkswirtschaftlichen Stabilisierung. Innenpolitisch schadete der Regierung jedoch der Beschluss, NATO-Flugzeugen freien Flug im bulgarischen Luftraum zum Bombardieren des Nachbarn Jugoslawien zu gewähren, was zu Protesten in der bulgarischen Bevölkerung führte. Die Wirtschaftsreformen führten andererseits jedoch zu einem massiven Anstieg der Arbeitslosigkeit, die von den nach wie vor von ehemaligen kommunistischen Funktionären geführten Massenmedien scharf kritisiert wurden und auch zu (allerdings nicht nachgewiesenen) Korruptionsvorwürfen führten. Am 7. April 1999 überstand seine Regierung ein Misstrauensvotum mit 139 zu 87 Stimmen ebenso wie am 16. Februar 2001 mit 135 zu 74 Stimmen.

Bei den Wahlen zur Nationalversammlung am 17. Juni 2001 unterlag die SDS der vom ehemaligen Zar Simeon II. (Simeon Sakskoburggotski) gegründeten Nationalen Bewegung Simeon der Zweite (NDSV). Dieser folgte ihm dann am 21. Juli 2001 als Ministerpräsident. Nach seiner Wahlniederlage, bei der die SDS 86 Parlamentssitze verlor, legte Kostow auch den Vorsitz der SDS nieder und trat später auch aus der Partei aus.

2004 gründete er mit den Demokraten für ein starkes Bulgarien eine neue politische Partei. Nach seiner Wiederwahl zum Vorsitzenden der DSB im Juli 2007 ist Kostow der maßgebliche Oppositionspolitiker gegen die Koalitionsregierung (2005–2009) der Bulgarischen Sozialistischen Partei, der NDSV und der Partei der türkischen Minderheit Bewegung für Rechte und Freiheiten (DPS). Er gilt als einer der schärfsten Opponenten von Ahmed Dogan, dem Vorsitzenden der DPS.

Am 11. Januar 2012 verabschiedete das bulgarische Parlament, auf Kostows Vorschlag, einstimmig eine Erklärung gegen die Assimilationspolitik des einstigen totalitären Regimes gegenüber der muslimischen Minderheit.

Nach den verlorenen Parlamentswahlen 2013, bei demem die DSB den Einzug ins Parlament verfehlte, gab Kostow seinen Rücktritt als Parteivorsitzender bekannt. Am 23. Juni 2013 wurde Radan Kanew auf Kostows Vorschlag zum neuen Vorsitzender der DSB gewählt.