Milošević påbörjade sin karriär i hemstadens Radnik Bijeljina innan han fick kontrakt med Partizan Belgrad. Han lade av med landslagsfotboll efter VM i Tyskland 2006. Den sista matchen blev mot Elfenbenskusten21 juni2006, då han spelade den andra halvleken av matchen. Matchen blev även Serbien och Montenegros sista match för mästerskapet, då de åkte ut i gruppspelet.
Milošević spelade även i VM 1998 och EM 2000, då laget hette Jugoslavien. Vid EM 2000 blev han delad skyttekung tillsammans med Patrick Kluivert; båda gjorde fem mål var men Kluivert spelade en match mer.
16 juni 2006 gjorde Milošević sin 100:e landskamp för Serbien och Montenegro vid VM 2006 i gruppspelsmatchen mot Argentina, vilket blev nytt rekord för landslaget.