Kariera zawodnicza

W 1982 na mityngu w Budapeszcie skoczyła 190 cm. Barierę dwóch metrów pokonała w 1984 roku w Sofii. Pierwszy wielki sukces odniosła jako dziewiętnastolatka – zdobyła złoty medal (skok na wysokość 197 cm) na odbywających się w styczniu 1985 w Paryżu zawodach World Indoor Games, które później zostały uznane za pierwsze halowe mistrzostwa świata w lekkoatletyce. Skok na taką samą wysokość dał jej także tytuł halowej mistrzyni Europy (Pireus, marzec). 18 sierpnia tego samego roku w Moskwie Kostadinowa skoczyła 2,06 metra, zaledwie centymetr mniej od ówczesnego rekordu świata ustanowionego w 1984 przez jej koleżankę z reprezentacji Bułgarii – Ludmiłę Andonową. Rok zakończyła zwycięstwem w Pucharze Świata rozgrywanym w Canberze. 25 maja 1986 Kostadinowa wyrównała wynik Andonowej, a niecały tydzień później – 31 maja ustanowiła samodzielny rekord świata skokiem na wysokość 208 centymetrów. Oba rekordowe skoki oddała w Sofii. W lipcu zdobyła złoty medal igrzysk Dobrej Woli. W sierpniu tegoż roku triumfowała z wynikiem 200 cm na XIV Mistrzostwach Europy rozgrywanych w Stuttgarcie.

W 1987 zdobyła złote medale Halowych Mistrzostw Europy we francuskim Liévin (luty, skok 197 cm) oraz na oficjalnych 1. Halowych Mistrzostwach Świata w Indianapolis z wynikiem 205 cm – halowy rekord świata (marzec). Na rozrywanych na przełomie sierpnia i września na stadionie olimpijskim w Rzymie 2. Mistrzostwach Świata w Lekkoatletyce Stefka Kostadinowa również zdobyła złoty medal i ustanowiła nowy, niepokonany do tej pory, wynik 209 cm.

20 lutego 1988 w Atenach poprawiła własny halowy rekord świata uzyskując 206 cm. W marcu zwyciężyła ponownie w Halowych Mistrzostwa Europy w Budapeszcie (marzec, skok 204 cm), więc na Letnie Igrzyska Olimpijskie 1988 pojechała jako absolutna faworytka. W Seulu zdobyła jednak srebrny medal (skok 201 cm) ulegając Amerykance Louise Ritter (203 cm). W 1989 w Budapeszcie ponownie zostaje halową mistrzynią świata (skok 202 cm).

Przez kolejne lata nie plasowała się na podium zawodów mistrzowskich – poza XXII Halowymi Mistrzostwami Europy w lutym 1992 w Genui, gdzie zdobyła srebrny medal ulegając Heike Henkel (obie skok 202 cm), która na odbywających się w lipcu i sierpniu tegoż roku Igrzyskach Olimpijskich w Barcelonie została także mistrzynią olimpijską. Kostadinowa zajęła na igrzyskach czwarte miejsce.

Swój wielki comeback zaliczyła na 4. Halowych Mistrzostwach Świata w marcu 1993 w Toronto, gdzie zrewanżowała się Heice Henkel i zdobyła złoty medal (obie skok 202 cm). Rok później, w marcu 1994 w Paryżu skok na wysokość zaledwie 198 cm dał jej tytuł halowej mistrzyni Europy.

W sierpniu 1995, kilka miesięcy po urodzeniu syna, zdobyła złoty medal na Mistrzostwa Świata na otwartym stadionie – rozgrywanych w szwedzkim Göteborgu (skok 201 cm). W 1996 trzydziestojednoletnia już Kostadinowa zdobyła jedyne brakujące jej trofeum – złoty medal olimpijski Igrzysk XXVI Olimpiady w Atlancie. W 1997 zdobyła jeszcze 5. złoty medal na Halowych Mistrzostwach Świata w Paryżu.

Wielokrotna reprezentantka Bułgarii w zawodach Pucharu Europy, w 1985 i 1987 triumfowała w konkursach skoczkiń wzwyż w finałach A.

W 1985 i 1986 triumfowała w mistrzostwach krajów bałkańskich na stadionie, w 1994 w halowym odpowiedniku tych zawodów.

W 1985, 1987 i 1993 była najlepszą skoczkinią wzwyż w cyklu Grand Prix IAAF. W łącznej punktacji wszystkich konkurencji najwyższe miejsce (drugie) zanotowała w 1985.

Ośmiokrotnie miała najlepsze wyniki na listach światowych na stadionie (1985–1988, 1992, 1993, 1996 i 1997 – wówczas ex aequo z Ukrainką Inhą Babakową), siedmiokrotnie w hali (1985, 1987–1989, 1993 – wspólnie z Niemką Heike Henkel, 1996 – ex aequo z reprezentującą Niemcy Aliną Astafei i 1997).

Jedenastokrotna mistrzyni Bułgarii (6 tytułów na stadionie oraz 5 w hali). Zwyciężyła w halowych mistrzostwach Węgier (1985) i Włoch (1987).

W czasie swojej kariery 197 razy przeskoczyła granicę dwóch metrów. Czterokrotnie była Sportowcem Roku w Bułgarii (1985, 1987, 1995, 1996), pięciokrotnie Sportowcem Bałkanów.

W 1987 została wybrana najlepszą lekkoatletką świata w pierwszej edycji plebiscytu IAAF World Athlete of the Year. Rok później anulowano ten wybór z powodu dopingu laureata męskiej nagrody – Bena Johnsona.

Działaczka sportowa

Po oficjalnym zakończeniu kariery sportowej w 1999 została działaczką sportową. Od 1999 była wiceprzewodniczącą, a w 2005 przewodniczącą Bułgarskiego Komitetu Olimpijskiego. Zastąpiła na stanowisku Iwana Sławkowa.

Od 13 października 2012 jest członkinią IAAF Hall of Fame.