Born in Dunfermline, Fife, Paterson was educated at Neville Lovett Community School in Fareham, Hampshire. He started his career in the youth system at Bournemouth before a number of clubs showed an interest. He then joined the Southampton Academy in 2007. At the end of the 2007–08 season, Paterson won Southampton Academy player of the season. He made his first team debut as a substitute at St Mary's Stadium, coming on for Jordan Robertson against Norwich City on 30 September 2008.
In his first year as a professional, Paterson caused controversy during an FA Cup tie against Manchester United on 4 January 2009, when he was given a red card for a tackle on Nemanja Vidić. He scored his first goal, shortly after coming on as a substitute, in a 3–0 victory at Ipswich Town on 3 March 2009. On 8 August 2009 he scored a goal for Southampton against Millwall in Southampton's first game of the 2009–10 campaign.
Paterson signed a two and a half-year deal with Southend United on 22 January 2010. He made his debut the following day against Wycombe Wanderers in a 1–1 draw. Paterson opened his scoring for Southend United at Milton Keynes Dons and followed this up with a goal against Charlton Athletic in the league.
Paterson started the 2010 season with two goals in a 3–2 victory against Bristol City in the League Cup on 10 August followed by two goals against Barnet in the Football League Trophy on 5 October 2010.
On 9 February 2011, Paterson joined League Two side Stockport County on loan. On 12 February 2011 Paterson made his Stockport debut against Bury and scored the opening goal in a 2–1 victory to lift The Hatters off the bottom of the table. On 5 March 2011, Paterson scored the equalising goal in a 2–1 win against Oxford United. A few days later, County confirmed that Paterson's loan had been extended until the end of the season. Paterson continued to try to keep Stockport County in the Football League with another goal against promotion chasing Stevenage on 9 April 2011. He returned to his parent club in early May after picking up an injury which ruled him out for the remainder of the season.
On 9 August 2011, Paterson joined Hamilton Academical on loan. The deal will run until 1 January 2012. On 13 August 2011 Paterson opened his scoring with Accies on his League debut in the 5–1 win over Ross County. Back from injury Paterson scored his second Accies goal with a right-footed curler to open the scoring in the 3–1 defeat of Queen of the South.
On 6 January 2012, Paterson joined Forest Green Rovers on loan. The deal ran for a month. Paterson was sent off on his debut against Mansfield Town the following day for serious foul play, only 12 minutes after coming on as a substitute in what proved to be his only appearance.
On 15 August 2012, Paterson completed his move to League Two side Burton Albion on a six-month contract deal.
Paterson made his Burton debut away to Rochdale on Saturday 8 September 2012 and marked his debut with a goal from twenty yards out to win the game for Burton. Paterson followed up his debut goal with another one against York City on 19 September by lobbing the keeper to record a 3–1 win. Paterson continued his good form with Burton by coming on as a substitute for Calvin Zola after 20 minutes against Dagenham & Redbridge. A poor back pass allowed Paterson to run through on goal and slot the ball home to make the score 2–1. The game finished in a 3–2 victory for the Brewers. On 26 October 2012 Paterson signed a new contract with Burton Albion to remain with the club until at least the end of the season. Manager Gary Rowett said, "Matt’s done really well. When he came here he was fifth choice striker initially. His hard work and performances have moved him up the list quite quickly and we’re delighted to have him on board for the rest of the season." Paterson returned to action following nearly six weeks out with a groin strain coming on as a 77th-minute substitute against Torquay United on Saturday 12 January 2013 and scored what was described as a 'magnificent winner and a better goal you will not see in the country' by Rowett, curling in a 22-yard right-footed goal. to win the game 2–1 for the Brewers. Paterson scored the opening goal in a 3–3 draw at Accrington Stanley on Easter Monday. Paterson latched onto a through ball which the defence failed to deal with and slotted home to get the equaliser early in the game.
Paterson continued his good form with a goal against Port Vale in the Brewers' 7–1 defeat. Manager Rowett said, 'Paterson came on and showed some real desire and his finish was sensational'. On Saturday 13 April, Paterson scored a 94th-minute winning strike that secured a play-off position for the club and also kept Burton in the automatic promotion positions in the League with only two games to go.
On 8 August 2013, Paterson decided on a move away from Burton Albion and move closer to his home in Hampshire and joined Skrill National Premier side Aldershot Town. In hunt of regular football and to lose his 'super-sub' moniker, Paterson elected to drop a league and take on the challenge of joining a side starting the new season with -10 points following their recent flirt with Administration. Paterson started the new season with the number 10 shirt and a fantastic performance away to Grimsby Town on the opening day of the season saw Aldershot take their first point of the season. Returning from injury Paterson started in the local derby against Woking on 24 August and immediately made an impact by scoring after 21 seconds. He followed this with a perfect cross to allow Brett Williams to score the second and winning goal in a 2–1 victory.
Paterson returned to the Shots side following an ankle and groin injury and four weeks on the sidelines to score the opener in the ill-fated FA Cup replay against Shortwood United, eventually losing the game 2–1. On 26 November, Paterson scored a 92nd-minute winner against high flying Braintree Town. Paterson came off the bench to clinically finish a good Shots move that saw him score the winner and give Aldershot their second league win a row. Following a poor 1–1 draw against Weston-super-Mare in the FA Trophy the replay took place on 3 December. Paterson came on early in the second half and scored the fourth goal (and his fourth goal of the season) in a thrilling 5–2 victory for the Shots.
Following an injury filled season, Paterson moved on a short term loan to Havant & Waterlooville to get 'match fit'; he returned to Aldershot mid-April.
During the summer of 2014, Paterson joined Gosport Borough. He scored his first goal for the club on 13 September 2014 against Weston-super-Mare in the Conference South, and achieved the first hat-trick of his career several weeks later in a 7-0 victory over Larkhall Athletic in the FA Cup. Paterson continued to attract interest from Football League teams with his goal scoring exploits at Gosport. Goals against Hemel Hempstead, Eastbourne Borough, Willand Rovers (FA Cup), Staines and a second hat trick of the season against Farnborough contributed to Paterson scoring 14 goals in 20 appearances Paterson took his goal tally to 17 at the end of December with the opening goal against local rivals Havant and Waterlooville on Boxing Day. Paterson continued his excellent season with goals against Bishops Stortford, Ebbsfleet United, Sutton United, St Albans and South League Champions Bromley. Paterson finished off the season with the last goal for his club in the Hants Cup Final bringing his goal tally to 25 for the season with him also credited with 28 'assists'. Paterson and Justin Bennett became the highest scoring partnership in the club's history with 58 goals between them.
Paterson joined Havant & Waterlooville for the 2015–16 season. This was a very poor season for Havant & Waterlooville who found themselves relegated after some horrendous defensive displays. Paterson managed 14 club goals in the season. Paterson won promotion with Havant & Waterlooville in the 16/17 back into the Conference South scoring 18 goals in the process. Following promotion he left the club to join Oxford City FC for the 2017–18 season.
A whirlwind start to the 2017–18 season saw Paterson score seven goals in his first eight games for his new club.