Wcześniej jeszcze przed rozpadem "starej" Jugosławii reprezentacja zdołała się zakwalifikować po sportowej walce na Euro 1992, jednak także z powodu międzynarodowych sankcji reprezentacja została wykluczona z mistrzostw na kilkanaście dni przed ich rozpoczęciem, a jej miejsce zajęła druga w swojej grupie eliminacyjnej Dania, która później zdobyła mistrzostwo Europy.
Zadebiutowała w kwalifikacjach do Mundialu 1998. Drużyna prowadzona przez Slobodana Santrača z Predragiem Mijatovicem, Miroslavem Djukicem, Sinišą Mihajlovicem i Darko Kovačevicem w składzie wprawdzie została wyprzedzona w grupie przez Hiszpanię, ale pokonała m.in. ówczesnych wicemistrzów Starego Kontynentu Czechów. Jugosłowianie grali ofensywnie i efektownie, i właśnie wtedy doczekali się przezwiska "Brazylijczycy Europy". W barażach nie dali szans Węgrom (7:1 i 5:0).
Na Mundialu zaprezentowali się przyzwoicie. W 1/8 finału po wyrównanym meczu i w dość pechowych okolicznościach (Mijatović nie strzelił karnego w ostatniej minucie) przegrali 1:2 z Holandią.
Dwa lata później, na Euro 2000, reprezentacja dowodzona tym razem przez 70-letniego Vujadina Boškova również odpadła w drugiej rundzie, a ich pogromcami (przegrali 1:6) tak jak w 1998 roku byli Holendrzy.