In 2004 he began his coaching career by taking charge of FK Zeta playing back then in the First League of FR Yugoslavia. After Montenegro declared independence in 2006, with FK Zeta he became first manager which won national title in the Montenegrin First League. Later, in 2007, he took charge of FK Mogren, a club he represented as player and that was competing in the Montenegrin First League. He immediately made an impact at Mogren by winning the Cup in 2008, and in the following season, 2008–09, their first ever national title. Later, during the 2010–11 season, he took charge again of FK Zeta leaving them in 4th place at the end of the season, with access to UEFA Europa League qualifying rounds. This active managerial experience led him to earn a call from Serbian SuperLiga side FK Vojvodina, as replacement for Zoran Milinković. He was officially announced as Vojvodina's main coach on 15 August 2011. Vukicevic resigned as a coach of Vojvodina on 13 April 2012 after Vojvodina lost to Borac Čačak in semi-finals of Serbian Cup.