Veličković je košarku počeo da trenira u zemunskom klubu Drvomarket, zatim je bio član Zemuna, a 2001. godine prelazi u Partizan. Uporedo sa juniorima crno-belih, Veličković je na početku karijere igrao i za Torlak u Prvoj B ligi, klub koji je tada bio drugi tim Partizana.
Za prvi tim Partizana je debitovao u sezoni 2004/05. Igrajući pod trenerom Duškom Vujoševićem, Veličković je u narednih pet sezona osvojio pet titula državnog prvaka, tri titule Jadranske lige kao i dva trofeja domaćeg Kupa Radivoja Koraća.
Za Partizan je u Evroligi debitovao tokom sezone 2005/06. U prvoj sezoni sa crno-belima takmičenje u Evroligi završava već u prvoj fazi. U drugoj sezoni je krajnji domet bila TOP 16 faza, a potom u sezonama 2007/08. i 2008/09. stiže do četvrfinala Evrolige gde su crno-beli eliminisani od Taukeramike i moskovskog CSKA.
I dok je u prve dve sezone u najjačem klupskom takmičenju imao mali učinak, u druge dve sezone gde su crno-beli stigli do četvrtfinala je bio jedan od vodećih igrača.
U Evroliginoj 2008/09. sezoni je dobio nagradu „Zvezda u usponu”, koja se dodeljuje najboljem mladom igraču ovog takmičenja. Njegove odlične partije došle su do izražaja u februaru 2009. kada je učestvovao u tri Partizanove pobede u mečevima TOP 16 faze, i tako dobio nagradu za najkorisnijeg igrača tog meseca. Veličković je sezonu 2008/09. završio kao najbolji strelac Partizana u Evroligi sa 11,5 poena po utakmici i kao drugi skakač, sa 5,1 skokova po utakmici. Veličković je takođe bio među tri najbolja igrača u ekipi po broju ukradenih lopti, asistencija i blokada.
Veličković je dao i značajan doprinos osvajanju tri domaća trofeja u sezoni 2008/09. Prvo je u februaru 2009. dobio nagradu za najkorisnijeg igrača Kupa Radivoja Koraća potom je u aprilu dobio nagradu za najkorisnijeg igrača fajnal-fora regionalne lige i konačno u završnici sezone je bio i najkorisniji igrač Superlige.
Veličković se 1. marta 2016. vratio u Partizan, potpisavši ugovor sa klubom do kraja 2015/16. sezone. S obzirom da je Partizan do tada završio svoja takmičenja u Jadranskoj ligi i Evrokupu, Veličković je nastupao samo u Superligi Srbije, gde su crno-beli poraženi u finalnoj seriji od Crvene zvezde. U septembru 2016. je potpisao novi jednogodišnji ugovor sa Partizanom, a nedugo zatim je postavljen i za kapitena. U sezoni 2016/17. sa crno-belima nije osvojio nijedan klupski trofej, ali je uvršten u idealnu petorku Jadranske lige za takmičarsku 2016/17, nakon što je prosečno beležio prosečno 11,3 poena i 5,2 skoka u ovom takmičenju.
Dana 18. septembra 2017. je potpisao novi jednogodišnji ugovor sa Partizanom. Svoj 400. meč u dresu Partizana je odigrao 18. februara 2018. u finalu Kupa Radivoja Koraća protiv Crvene zvezde. Partizan je na ovom meču slavio rezultatom 81:75 pa je tako osvojio prvi trofej nakon četiri godine, a Veličković je meč završio sa 13 postignutih poena.
To je bio jedini trofej koji je Veličković osvojio u sezoni 2017/18, ali je kao i prethodne sezone ponovo uvršten u idealnu petorku Jadranske lige nakon što je beležio prosečno 12,1 poena i 5,3 skoka po meču.
U avgustu 2018. je ponovo produžio ugovor na još godinu dana. U sezoni 2018/19. sa crno-belima osvaja još jedan Kup Radivoja Koraća. U ovoj sezoni je imao nešto slabiji lični učinak, pa je u Jadranskoj ligi beležio tek 4,3 poena dok je u Superligi imao nešto bolji učinak sa 8,3 poena prosečno po meču. Kao i prethodnih godina, Veličković je tokom leta 2019. produžio ugovor sa Partizanom.
U sezoni 2019/20. spisku osvojenih trofeja dodaje Superkup Jadranske lige, kao i još jedan Kup Radivoja Koraća.
Kurir sport
NE PROPUSTITE
