Petković started playing by SFR Yugoslavia youth teams when he was 15 years old. In that age, he even scored one of the fastest goals in football, after just three seconds in a match against Cyprus. He was later called to 1992 Toulon Tournament, alongside players like Savo Milošević, Zoran Mirković, Željko Cicović, Elvir Bolić, Spira Grujić, Mitko Stojkovski, Srđan Bajčetić, Miladin Bečanović, Igor Taševski, Sretko Vuksanović and Željko Tadić. His team made a runner-up campaign, in which Petković scored two goals in a 3–0 triumph over United States (against players such as Brad Friedel, Claudio Reyna, Alexi Lalas and Cobi Jones).