Stefka Kostadinova osvojila je zlatnu olimpijsku medalju na OI u Atlanti 1996., pritom postavivši olimpijski rekord za žene koji je iznosio 2.05 m. Također je osvojila srebrnu medalju na OI u Seoulu 1988. Dvostruka je dvoranska svjetska prvakinja. Prvi put je postala prvakinja na SP-u 1987., a drugi put na SP-u 1995.
Kostadinova i dalje drži svjetski rekord u ženskom skoku u vis s preskočenih 2.09 metara koje je preskočila na Svjetskom prvenstvu 1987. u Rimu. Njezin svjetski rekord je jedan od najstarijih u suvremenoj atletici. Ukupno je postavila sedam svjetskih rekorda - tri na otvorenom i četiri dvoranska. Preskočila je 2 metra više od stotinu puta, što je još neponovljeni uspjeh u ženskom skoku u vis. Ovaj uspjeh dobiva na težini još više znajući da većina skakačica nikad ne preskoči dva metra.
Kostadinova je proglašena bugarskomsportskom osobom godine četiri puta (1985., 1987., 1995. i 1996.). Također je uvrštena u Top 10 (hrv.Najboljih deset) atletičarki 20. stoljeća, prema Međunarodnom savezu atletskih federacija (IAAF).
Rodila je sina Nikolaja 1995., samo nekoliko mjeseci prije osvajanja zlatne medalje na Svjetskom atletskom prvenstvu iste godine. Četiri godine poslije, 1999., razvela se od dugogodišnjeg supruga, Nikolaja Petrova. Iste godine odlučila je i službeno prekinuti profesionalnu karijeru, iako nije nastupila ni na jednom važnijem sportskom natjecanju od Svjetskog dvoranskog prvenstva 1997.
11. studenog2005. izabrana je za predsjednicu Bugarskog olimpijskog odbora zamijenivši Ivana Slavkova koji je otpušten od strane Međunarodnog olimpijskog odbora zbog nepoštivanja etike.
.svg){kind=small}