Veličković started playing basketball for KK Drvomarket in 1996. Then he played for Zemun from 1998 to 2001 before signing with KK Partizan in 2001.
Partizan
Veličković made his professional debut with Partizan during the 2004–05 season. He made his EuroLeague debut on 3 November 2005 against Pau-Orthez, scoring 2 points. In the 2007–08 season, Veličković had a bigger role in the team. On 16 January 2008 in an 88–87 loss to Lottomatica Roma, he scored 22 points and 9 rebounds, his best game in new season. He led the team with 11 points and 4 rebounds to the EuroLeague Quarterfinals in an 82–73 win over Panathinaikos on 19 March 2008. Over the season, in 22 EuroLeague games, Veličković averaged 10.6 points, 6.9 rebounds, and 1.6 assists per game. As of 2018, Veličković was the only player to not be drafted by any NBA team in an NBA Draft. In February 2009, he won the Serbian Cup in an 80–65 win over Crvena zvezda and he was the MVP of the competition. On 31 March 2009, Veličković scored a career-high 26 points against CSKA Moscow. On 18 April 2009, he helped his team with 17 points and 8 rebounds in a 63–49 win over Cibona to win the 2008–09 ABA League trophy. For his performances, he was named the Adriatic League Final Four MVP. In April 2009, he won the EuroLeague Rising Star award for the 2008–09 season. Partizan finished the season by winning 8th consecutive Serbian League title, after once again defeating their archrivals, Crvena zvezda, 3–2 in the league's finals series. Veličković was named the Serbian Super League MVP and MVP of the Finals.
Veličković was seen as the first target of Real Madrid's new coach Ettore Messina. His transfer, with the signing of a two-year contract with an option for a third one, was made official on June 23, 2009. In June 2012, Real Madrid decided to release Veličković due to the numerous injuries.
2013–2016
On January 31, 2013, he signed a short-term contract with the Serbian team Mega Vizura. In the game against the Radnički Kragujevac on May 12, he recorded season-best 37 points while shooting 11 from 16 from the field and grabbed 8 rebounds. On August 5, 2013, Veličković signed a contract for the upcoming season with the German team Brose Baskets. He was released on February 20, 2014. Four days later, he returned to Mega Vizura for the remainder of the season. On June 21, 2014, he signed a one-year contract with the Turkish team Trabzonspor. On May 24, 2015, he extended his contract with Trabzonspor for one more season.
Return to Partizan
On March 1, 2016, Veličković left Trabzonspor and signed with his former club Partizan for the rest of the season. On 7 May, Veličković made his re-debut for Partizan against Borac Čačak and recorded 9 points, 2 rebounds and 3 assists. On September 14, 2016, Veličković re-signed with Partizan for the 2016–17 season, and he became the new team captain. In March 2017, he was selected for the ideal team of the 2016–17 ABA League season, after averaging 11.2 points, 5.5 rebounds and 1.9 assists over 26 games. On September 18, 2017, he re-signed with Partizan for the 2017–18 season. On 18 February 2018, in Final of 2017–18 Radivoj Korać Cup, Veličković played his 400th match for the club. He helped the club to win their first trophy in almost four years, with 13 points, 7 rebounds and 1 assist in an 81–75 win over Crvena zvezda. In 21 games of the 2017–18 ABA League First Division, he averaged 12.1 points, 5.3 rebounds and 2.4 assists per game. On August 10, 2018, he signed one-year contract extension with Partizan. In 2018–19 season, after struggling with conditioning and game shape in the beginning of the season, he regained trust of head coach Andrea Trinchieri and saw increased minutes until the end of the season. In the 2018–19 ABA League First Division, he averaged 4.8 points, 2.6 rebounds and 1.1 assists over 11.8 minutes played per games. Partizan defended the Radivoj Korać Cup trophy, but failed to win championships in ABA League and Serbian League. On January 18, 2020, he broke the club record with 472 games played for the club, surpassing Petar Božić at the all-time list.
