Vujadinović begon zijn carrière bij Rode Ster Belgrado. Later speelde hij voor FK Rad (Belgrado), FK Zeta (Podgorica) en FK Radnicki Pirot (Pirot).
In mei 2007 maakte hij transfervrij de overstap naar CSKA Sofia, en tekende hij een driejarig contract in de Bulgaarse Premier League.
In augustus 2008 maakte Udinese bekend dat zij Vujadinović voor € 1 miljoen overnamen. Udinese bood hem een 5-jarig contract aan.
In september 2009 werd hij uitgeleend door Udinese aan Unirea Alba Iulia, uit Roemenië.
Voor het seizoen 2010-2011 werd hij ook uitgeleend, aan de Schotse club Aberdeen. Die hadden Vujadinović gecontracteerd als vervanger voor Richard Foster. De eerste aanvraag voor een werkvergunning werd afgewezen, een vergunning werd wel verleend.
Op 15 januari 2011 werd de huur van Vujadionović verlengd tot het einde van het seizoen. Onder managers Mark McGhee en vervolgens Craig Brown, maakte hij 18 competitie optredens voor Aberdeen en ook in de halve finale van de Scottish Cup en de Schotse League Cup. Aan het einde van het seizoen keerde hij weer terug naar Udinese.