Vukov begon zijn loopbaan in 1989 bij Vojvodina Novi Sad. In 1991 nam hij met het Joegoslavisch olympisch elftal deel aan de Middellandse Zeespelen (vierde plaats). Tussen 1993 en 1999 speelde hij bij FC Volendam.[1][2] In zijn eerste twee seizoenen speelde hij geregeld maar hierna kwam hij steeds minder aan spelen toe. Pas na de degradatie van Volendam, in 1998, werd hij weer meer voor wedstrijden geselecteerd.[3]