King started his journey in Lincoln City's U9's team. He went up through the ranks for ten years. He also played for East Coast Juniors as a young kid once scored 50 goals from midfield in one season. King signed his first professional contract on 19 April 2008. Later that day, he made his first start for Lincoln and scored against Brentford in the 39th minute of the game. Lincoln later went on to win this match 3–1. He joined Boston United on loan on 8 January 2009 till mid-March. He joined Accrington prior to the 2009–10 season. Gary enjoyed his first goal for Accrington against the team from where he was born, Grimsby Town. On 7 June 2010 he signed for Hinckley United. On 12 November 2010 he signed non-contract terms with Louth Town, marking his debut for the club by scoring a last minute winner in the 2–1 victory at Appleby Frodingham in the Northern Counties East League Division One clash on 13 November 2010. After two further appearances for the club, one in the league one in the cup, he moved on, joining Stamfordat the beginning of December 2010. However, with inclement weather preventing any competitive football for the club, a seven-day notice for King's services was put in by Harrogate Town shortly before Christmas and he duly linked up with the Football Conference North club. King was released from Harrogate Town on 13 May 2011 after his contract was not renewed for the new season. In July 2011 it was announced that he had rejoined Stamford. He returned to Stamford in January 2012 On 18 February 2012, he agreed to join Corby Town on a dual-registration deal with Grantham Town. In May 2012, he agreed a deal to rejoin Stamford. He moved on to join Spalding United, marking his debut by scoring twice in a 2-1 FA Vase 4th Round victory at Ely City on 29 January 2013. He returned to former club Corby Town in March 2013, joining the club on a dual-registration deal. In August 2013 he joined Brigg Town but swiftly departed to join Grantham Town, making a goalscoring debut in the club's opening day 2–1 defeat at Ashton United on 17 August 2013. On 9 December 2013, he moved on to join Coalville Town However, his spell with the club was short and he returned to Grantham Town in January 2014. In April 2014 he was on his travels again, joining Deeping Rangers for whom he would score twice for in their 4–5 defeat to Huntingdon Town in the United Counties League Cup Final on 5 May 2014. He agreed to join Holbeach United ahead on the 2014–15 season and, after completing a whole season with the club, agreed new terms for the 2015–16 season. In December 2015 he moved on to join Lincoln United. In January 2017 he joined Stamford but was quickly on the move again, joining Cleethorpes Town ahead of their FA Vase quarter final tie at Southall which the club would win 5–2 with King debuting as a substitute. On 18 March 2017, his first-minute lob secured the club's place at Wembley Stadium as they went through to the FA Vase Final with a 1–0 home victory, and 2-1 aggregate score, over Bromsgrove Sporting. He joined Spalding United for a second spell in May 2017, remaining with the club until the beginning of November 2018. In January 2019, he rejoined Lincoln United, debuting in the club's 5–0 defeat at Marske United on 19 January 2019.
