Gary Megson embarked on a career in management in 1995, when, while still registered as a player at the club, he became assistant to Norwich City manager John Deehan. Following Deehan's departure towards the end of the 1994/95 season, Megson was placed in temporary charge of the struggling FA Carling Premiership club. In five matches as caretaker, he could not save a depleted Canaries side from relegation, losing four and drawing one.

With relegation confirmed, Megson left Norwich, retired from playing and was appointed Chris Kamara's assistant at Bradford City. He soon returned to Carrow Road however, taking the managerial reins from Martin O'Neill, after the Northern Irishman's spell in charge came to an abrupt end in December 1995. Megson left the club in the summer, taking up the vacant Blackpool post soon after.

He spent a year at Bloomfield Road, achieving a seventh place finish for the old Division Two side, before moving on to Stockport County. In his first season with the Hatters, Megson led the club to an eighth place finish in the old Division One. The 1998/99 season, his second at the club, the Edgeley Park outfit finished 16th and Megson subsequently departed.

The former Sheffield Wednesday star was appointed Stoke City manager shortly after leaving Stockport, and got off to a flying start. The team suffered only one defeat in the first 13 matches of the 1999/2000 season, and looked likely promotion contenders. However, following a takeover, Megson was sacked so new chairman Gunnar Thor Gislason could bring in a manager of his own.

Megson found a new club at the tail end of the season, helping West Bromwich Albion sidestep relegation from Division One, thanks to a crucial final day win. The 2000/01 season saw the Baggies make the play-offs, only to be beaten by Megson's future club Bolton Wanderers over the two-legged semi-final. The Hawthorns outfit were more successful during the following campaign, winning promotion to the Barclaycard Premiership having finished the season in second place. Following that achievement, Megson won the Division One Manager of the Year award.

The club found their first Premiership spell tough, and the 2002/03 season saw the side relegated back to the Championship. They bounced back and mounted a successful promotion campaign the following season, and renewed their top-flight status for the 2004/05 season. The new season got off to a bad start, and after announcing he had no plans to renew his contract, Megson left the club in October 2004.

In early 2005, he returned to Nottingham Forest, the club where he had spent time as a player over 20 years before. Prior to his arrival, Forest were struggling in the Championship and he was unable to turn the club's fortunes around. Forest were relegated to the third tier of English football for the first time and Megson resigned in February 2006.

After an 18 month spell out of the game, he joined Leicester City in September 2007. He spent six weeks at the Walkers Stadium before moving to Bolton to replace Sammy Lee.

He guided the Trotters to a 16th place finish in the 2007/08 season, a good result as they had looked likely relegation contenders. He also helped the side get to the last 16 stage of the UEFA Cup, for the first time in their history.