Velička began his career at FBK Kaunas. He had spells on loan at Russian side Anzhi Makhachkala and Kazakhstani outfit Irtysh Pavlodar. During his time in Kaunas he played over 150 games and scored over one hundred goals for the club.
Velička joined Heart of Midlothian in the summer of 2006 in a loan deal and made his debut on 9 September 2006 in an SPL against St Mirren during a 1–0 defeat, coming on as a substitute for Neil McCann. On 15 October, Velička scored two goals in the Edinburgh derby against Hibernian, earning 10-man Hearts a draw. He also scored in the 1–1 draw with Dunfermline Athletic on 28 October. He netted yet another Hearts goal at Celtic Park, in a 2–1 defeat to the league champions, however Velička became Hearts top goalscorer as a result of his goal. He scored his first hat-trick for Hearts in a 4–0 Scottish Cup third round win against Stranraer on 6 January 2007. Initially, his loan deal at Hearts ended without being renewed but he returned for the 2007–08 season days later. In the early part of that season he was used as an impact substitution to great effect, scoring on numerous occasions after coming off the bench, in particular when scoring both goals in the 2–0 victory away to Celtic in the Scottish League Cup quarter final on 31 October. He netted the 500th goal Hearts have scored in the SPL against Rangers at Ibrox.
Rumours in the press linking Velička with a move to Norwegian club Viking FK proved true when it emerged that Hearts had accepted a bid of £1 million. On 26 February 2008 he signed a four-year contract with Viking and completed the move. Velicka scored his first goal for Viking in his debut match against Hamarkameratene on 6 April 2008 but Viking lost the match 3–2, and Velicka stated that he could not be happy about his goal because of the team failing to win the match. He played 18 games and scored six goals in Norway.
Rangers
On 14 June Viking accepted a bid believed to be around £1 million from Glasgow side Rangers for Velička. They received permission to hold signing talks with a view to agreeing personal terms over a move. He signed a three-year contract on 16 June and became a Rangers player on 14 July on their tour of Germany a day after he finished the Norwegian spring part season with Viking FK. Velička made his debut for the club in a UEFA Champions League qualifier on 30 July 2008 against his old team FBK Kaunas. He came on as a substitute in the second leg, and after missing an easy chance, Kaunas scored to knock Rangers out. Velička had a better time when he played his first league game for the club, scoring the winning goal in a 1–0 win over Falkirk. Despite the goal and a start the following week against former club Hearts, Velička fell out of favour at Ibrox and did not make another first team appearance until an away league match at Falkirk in April 2009. His next start came the following weekend, against Motherwell and he opened the scoring in the first two minutes of the match. He scored again the following week against Hibernian at Easter Road in a 3–2 win for the Gers, and bagged his third in three games with a fine finish against St Mirren in the Scottish Cup. He then scored another against former club Hearts, to make it four goals in four starts.
On 17 August 2009 Velička joined Bristol City on a year-long loan, as his first team opportunities were limited at Rangers. He made his debut for City against Queens Park Rangers the following day as a 64th-minute substitute. He lasted just minutes before injuring himself and leaving the field on a stretcher with a suspected serious knee injury. The 2009–10 season for Velička was confirmed as over as scans showed he had suffered an anterior cruciate ligament injury.
On 31 August 2010 Velička joined Aberdeen on a season-long loan deal from Rangers. He scored his only goal for Aberdeen against Inverness Caledonian Thistle on 9 November 2010. On 31 January 2011, it was announced that Velička had been released from his loan contract with Aberdeen and became a free agent.
Later career
On 11 February 2011 Velička joined FK Ekranas on a three-year deal. At the beginning of the 2013/2014 season Velička bought out the last six months of his contract at Lithuanian side FK Ekranas in order to return to Glasgow, Scotland.
International career
Velička made his international debut as an 80th-minute substitute, replacing Valdas Trakys, during a 1–1 draw against Moldova in Kaunas on 16 August 1998. He had to wait almost four years for his second cap which came in April 2002, against Yugoslavia. He scored his first goal in a game against Estonia on 3 July 2003 in Valga, during a 5–1 win. He had been on the pitch five minutes before netting the third in the 72nd minute.
International goals
Scores and results list Lithuania's goal tally first
