Stojković's numerous comedic portrayals of the "small man fighting the system" made him popular with Serbian and ex-Yugoslav audiences, most of them coming in collaborations with either director Slobodan Šijan or scriptwriter Dušan Kovačević, or both.Belgrade born and bred Stojković, a well-known theatre actor by the mid-1960s, started his film career with the 1964 feature Izdajnik (lit. "The Traitor"). A string of TV and minor film roles ensued, with the most important ones coming in guise of being a father figure to the main protagonist – Čuvar plaže u zimskom periodu (Beach Guard in Winter, 1976), Pas koji je voleo vozove (The Dog Who Loved Trains, 1977) being the most recognizable ones – as well as the part in critically well-received Majstor i Margarita (Il Maestro e Margherita, 1972). He also fulfilled the fatherly role in an immensely popular TV show Grlom u jagode. The show originally aired in 1975 and kept finding its audience through numerous reruns in the 1980s and the 1990s. Most notably, he almost stole the show as the minor antagonist in Goran Marković's urban classic Nacionalna klasa do 750 cm³ (National Class Category Up to 750 ccm, 1979).Arguably, Stojković delivered some of his finest work while working with the director Slobodan Šijan, who was in turn most successful when working with Dušan Kovačević scripts. Kovačević, a talented playwright with a special gift for biting satire, had a knack for writing characters which Stojković could perfectly translate to screen. The combination of those three creative talents yielded some of Serbia's most memorable cinematic efforts to date.

Šijan, who previously worked with Stojković on a several TV productions, made his big screen debut with Ko to tamo peva (Who's Singing Over There?, 1980), a farcical comedy set at the beginning of World War II in then Yugoslavia. In a strong cast ensemble, Stojković distinguished himself with role of a Germanophile bus passenger on the way to Beograd in the eve of 6 April 1941 – the day that Belgrade was bombed by the Axis Powers marking Yugoslavia's entry into the war. Ko to tamo peva was released to great critical and commercial success, and has won two awards at the Montreal World Film Festival in Canada. To this date, it is considered one of the finest Yugoslavian films ever.

The success of Ko to tamo peva opened new doors for Stojković, who then established his film star status with a string of critically acclaimed roles. He appeared in Goran Paskaljević's dark comedy about rehab from alcoholism, Poseban tretman (Special Treatment, 1980), and then reunited with Šijan for another high-water mark of Serbian film, the black comedy Maratonci trče počasni krug (Marathon Family). The film, a humorous piece about a family whose undertaking business is being threatened by the local mobster was another smash success for Šijan and Stojković, and it retains its cult status to this day. Stojković again delivered a strong performance in a star-studded production, flawlessly portraying the head of the family in waiting: Laki Topalović.