Velikonja started to play football at Gorica. Coming through their youth system, he was promoted to the senior squad in 2006–07. In his first season, he took part in seven matches, scoring one goal. Next year, during the 2007–08 season, Velikonja played 31 matches, scoring five goals. During the 2008–09 campaign, Velikonja played 32 matches and scored a total of 17 goals, finishing the campaign as the top goal scorer in the Slovenian PrvaLiga. In October 2009, in a league match against Koper, he sustained a serious knee injury which caused him to miss the majority of the 2009–10 season. He was not available to the team up until the end of April 2010, four rounds before the end of the season, when he returned to the pitch as a late substitute in a league match against Drava Ptuj.
During the 2010 summer transfer window, it was speculated for the first time that Velikonja could join Slovenian PrvaLiga side Maribor, however, the deal was eventually not carried out and Velikonja stayed with Gorica for the start of the 2010–11 season. He then prepared himself for the new season, putting his injury behind him, as by the end of 2010 he had played a total of 18 league matches for Gorica with an average of over 89 minutes per round, scoring five goals in the process. On 17 January 2011, during the winter transfer window, Velikonja was signed by Maribor in a deal that included an undisclosed transfer fee and a player, Vito Plut, going the other way. Velikonja has signed a contract with Maribor until 31 December 2013. He played his first league match for the new club on 26 February 2011, and scored one goal in a 4–2 victory against Rudar Velenje.
On 12 July 2012, Velikonja signed a four-year contract for Football League Championship side Cardiff City. The whole transfer is reportedly worth €3.6 million and Zlatko Zahovič, director of football at Maribor, stated that the Velikonja transfer was a record high for the Slovenian PrvaLiga at the time. Maribor reportedly received a compensation of €2 million, with Velikonja earning around €400,000 per season for a total of €1.6 million in four years with the Welsh side. He joined his new club on 25 July after the second qualifying round of the 2012–13 UEFA Champions League. He made his debut on 21 August in a 0–0 draw against Brighton & Hove Albion. Despite a prolific goalscoring record for Cardiff's Development Squad, Velikonja found first-team opportunities limited during his first season at the club, but was rewarded for his patience with a start up front at Hull City on the final day of the title-winning campaign, which resulted in being substituted at half time after an ineffective performance.
After months of waiting for his Premier League debut, Cardiff City loaned him to Rio Ave in January 2014 until the end of the season. He played two cup finals with Nuno Espirito Santo's team but lost both the Taça de Portugal and Taça da Liga finals against Benfica.
With Cardiff City swiftly relegated to the Championship, Velikonja was loaned out again in January 2015. Former Slovenia national team manager Slaviša Stojanović brought Velikonja to Lierse. After the team was relegated from the top division in 2014–15, Velikonja scored eight goals in his first eight appearances of the season during the 2015–16 Belgian Second Division. With mid-table Lierse struggling in the fight for promotion, Velikonja broke his all-time goalscoring record for a single season by scoring his 21st goal against Heist on 19 March 2016. Velikonja finished the season with a record goal tally of 24 and as the league's top scorer for the second time in his career. Lierse finished seventh and avoided the drop to Belgian amateur league football. He was voted as the player of the season by Lierse fans.
Velikonja returned to Slovenia for the 2016–17 season, accepting an offer from Olimpija Ljubljana. He scored on his debut for Olimpija against AS Trenčín in the second round of the UEFA Champions League qualifying campaign.
International career
Velikonja was a member of the Slovenian youth national teams from under-18 to under-21. On 12 August 2009, Velikonja made his full international debut for Slovenia in a 2010 FIFA World Cup qualification match against San Marino.
