קוסטוב הצליח לייצב את הכלכלה הבולגרית ונרשמה עלייה בתוצר המקומי הגולמי. ממשלו ביצע שורת רפורמות שכללו בין השאר הפרטה של חברות ממשלתיות והחל משא ומתן על הצטרפות בולגריה לאיחוד האירופי. עם זאת, הועלו בבולגריה טענות כנגד ממשלו של קוסטוב בדבר אי סדרים ושחיתות כלכלית. בנוסף, נמתחה על קוסטוב ביקורת על מהירותו של תהליך ההפרטה, אשר הוביל לפשיטת רגל של לא מעט חברות שהופרטו. בבחירות שנערכו ב-2001 הפסידה מפלגתו של קוסטוב ל"תנועה העממית ליציבות וקידמה" בראשות סימאון סקסקובורגותסקי.
קוסטוב התפטר מראשות מפלגת איחוד הכוחות הדמוקרטיים וב-2004 הקים מפלגה חדשה בשם "דמוקרטים למען בולגריה חזקה", אשר הציגה עמדות ימניות, והוא נבחר מטעמה לפרלמנט.