Als Spieler

Mit 20 Jahren begann er beim jugoslawischen Spitzenklub Metaloplastika Šabac. 1988 wechselte er nach Spanien zum FC Barcelona und 1993 zu BM Granollers.

Als Trainer

Nach seinem Karriereende im Jahr 1995 wurde er Trainer bei Metaloplastika Šabac und ab 2000 beim spanischen Erstligisten BM Ciudad Real. Diese Position verlor er im April 2002, nachdem er im Final-Hinspiel im Europapokal der Pokalsieger nach dem Spiel gegen die SG Flensburg-Handewitt den Flensburger Spieler Lars Christiansen niedergestreckt hatte. Anschließend war er auf den am Boden liegenden Lars Krogh Jeppesen getreten. Er erhielt dafür von der EHF eine zehnmonatige Sperre und 9.000 Euro Geldstrafe.

2005 führte er die Jugend-Nationalmannschaft von Serbien-Montenegro zum ersten Jugend-Weltmeisterschaftstitel. Bei der Europameisterschaft 2004 in Slowenien gewann die von ihm trainierte serbisch-montenegrinische Nationalmannschaft gegen den späteren Europameister Deutschland im Eröffnungsspiel 28:26. Seine Mannschaft wurde dann Sechster. Bei der Weltmeisterschaft 2005 in Tunesien wurde seine Mannschaft Fünfter. Bei der Europameisterschaft 2006 in der Schweiz erreichte seine Mannschaft nur den neunten Platz. Dies führte wie auch der Vorwurf, er hätte seinen Spielern ein absichtliches Verlieren im Spiel gegen Kroatien vorgeschlagen, mit zu seiner Ablösung durch Jovica Cvetković. Mit ihm tauschte er quasi seinen Arbeitgeber, denn Veselin Vujović trainierte anschließend die mazedonische Mannschaft von RK Vardar Skopje, wo Jovica Cvetković zuvor als Trainer tätig war. Am 23. November 2008 attackierte Vujović nach einem Europapokalspiel zwischen Vardar Skopje und den Kadetten Schaffhausen die Schiedsrichter, woraufhin er für ein Jahr gesperrt wurde und eine Geldstrafe von 3.000 Euro erhielt. Im Januar 2010 verließ er Skopje und trainierte bis Dezember 2010 den katarischen Verein al-Sadd Sports Club. Im April des folgenden Jahres übernahm er erneut das Traineramt von RK Vardar Skopje. Nachdem Vujović im Sommer 2013 in die Vereinigten Arabischen Emirate zum Verein al Shabab gewechselt war, wurde er im September 2014 Trainer des kroatischen Klubs RK Zagreb. Ab Mai 2015 trainierte er zusätzlich die slowenische Nationalmannschaft. In der Saison 2017/18 trainierte er zusätzlich den slowenischen Erstligisten RD Koper 2013. In der Saison 2018/19 trainierte er den serbischen Erstligisten RK Železničar Niš. Im September 2019 übernahm er erneut RK Zagreb. Im November 2019 trennte sich der slowenische Handballverband von ihm. Nach der Saison 2019/20 beendete Vujović aus persönlichen Gründen sein Engagement bei RK Zagreb. Seit Januar 2021 trainiert er den bosnischen Erstligisten RK Borac Banja Luka. Im Sommer 2021 übernahm er zum dritten Mal das Traineramt von RK Vardar Skopje. Dort wurde er im Dezember 2021 freigestellt.

Vujović trainiert seit dem März 2022 die iranische Nationalmannschaft.