He made his senior debut for Walsall on 31 August 2010 in a 2–1 defeat to Chesterfield in the Football League Trophy. He made his league debut 4 days later, in a 1–0 defeat to Colchester United. His first goal for the club came over a year later, as he scored in a 1–1 draw against Huddersfield Town on 5 November 2011. His second and third league goals came in a 2–1 loss to Bury on 2 January 2012, and in a 2–2 draw against Sheffield Wednesday on 20 March. His first goal of the 2012–13 season came on 1 September, as he opened the scoring in a 2–2 draw against Brentford. His scoring rate increased from his previous two seasons, and he scored his seventh goal of the season on 1 January 2013 to give Walsall a 1–0 win against Stevenage. He then stated that his target for the season was to score 10 goals, and that the team had regained their confidence following three wins in the last four games. On 2 February, he scored twice in a 3–1 win against Oldham Athletic.On 1 April, he gave a superb performance against Coventry City by scoring twice in a 4-0 win
On July 2 2013, Paterson signed for Nottingham Forest on a three-year deal. The fee was undisclosed, however it was believed it was a six-figure fee with add-ons taking the total amount beyond £1M. He scored his first goal for the club in a pre-season friendly against Belgian side Royal Antwerp on 20 July.