Downing was born in Taunton, Somerset and came through the youth system at West Bromwich Albion. He signed a professional contract lasting until June 2012, with an option of a further year in the club's favour. He made the bench for a 0–0 draw against Blackburn in the Premier League on 24 May 2009. Downing went on a one-month loan deal to Hereford United on 25 January 2010, along with West Brom teammate Lateef Elford-Alliyu. He was given the squad number 16, and made his debut on 2 February in a 2–0 win against Lincoln City at Edgar Street. He was sent off on his final appearance, a 5–0 loss to eventual league winners Notts County on 27 February. He made six appearances during his loan spell.Paul Downing in 2009/2010"/> Between November 2010 and April 2011, Downing signed on loan for two successive spells with Rotherham United and Shrewsbury Town but made no senior appearances for either club before returning to West Brom. On 3 November 2011 he signed on loan for League Two side Barnet, initially on a one-month deal. He made his debut on 8 November in a 2–0 win in the Football League Trophy against Cheltenham Town. On 17 November Barnet extended the loan deal to allow him to remain there until 2 January. On 19 January 2012 the loan deal was extended again to allow him to remain at Barnet until 28 February. On 29 February the loan deal was extended again, this time until the end of the season. He was sent off for the second time in his career during a 1–1 draw with Rotherham on 3 March. When Downing returned to West Bromwich Albion at the end of the 2011–12 season the club announced that they were not offering him a new contract. On 24 May 2012, Downing was released after three years at the club, having never made an appearance for the first team.
On 27 June 2016, after declining a new contract with Walsall, Downing joined fellow League One side Milton Keynes Dons on a free transfer, signing a two-year deal. Downing made his league debut for the club on 6 August 2016, in a 0–1 away win against Shrewsbury Town.
On 31 August 2017, Downing initially joined fellow League One club Blackburn Rovers on a season-long loan. On 8 January 2018, Downing joined the club permanently on a one-and-a-half-year deal for an undisclosed fee. On 15 May 2019 it was announced that Downing will leave at the end of his contract. Downing was seen by many of his Rovers teammates to be something of a mentor figure, leading him to be known among the squad as Uncle Paul.
On 24 January 2019, it was announced that Downing had been loaned to Doncaster Rovers in League One for the rest of that season.
Portsmouth
On 21 June 2019, it was announced Downing had signed for League One side Portsmouth on a free transfer, signing a three-year contract after being released by Blackburn Rovers.
