In 1991 Connolly was appointed as an assistant coach at Melbourne Football Club. He then became the head coach of the under 18 Eastern Ranges team in 1992. 1995 saw Connolly coach the Victoria Metro team in the National Under 18 Championships.
1996 saw Connolly join the Hawthorn Football Club as their reserves coach. In 2000 he was elevated to the No 1 assistant coach for the league team. In 2001 Connolly coached one game for the Hawthorn Football Club (in Round 17 against Carlton) in the absence of the regular head coach, Peter Schwab, who suffered from an irregular heartbeat. Hawthorn won the game, with Ben Dixon kicking the winning goal after the siren.
Connolly took over the coaching reins for the 2002 season at the Fremantle Football Club following their dismal wooden spoon season of 2001 . in his first year they struggled a bit and finished 13th. However he took the club to its first ever finals series in 2003, but was beaten comprehensively by Essendon at its home ground of Subiaco Oval in the First Elimination Final .
In the years since Connolly has been much maligned for not building on that initial finals appearance, with the Dockers finishing 9th in 2004 (missing the finals), and finishing 10th in 2005. In 2005, despite a late-season surge following a 5-win, 9-loss start when Connolly was under immense pressure from fans, they again missed the finals.
The Dockers' failure to live up to their perceived potential under the guidance of Connolly led to some off-field changes prior to the 2006 season, with two high-profile assistant coaches from Essendon in Mark Harvey and Robert Shaw joining the Dockers coaching staff. On-field, however, Connolly made only three changes to the playing list, trusting the young list that has been developed over the past four seasons. Despite an indifferent start to the season and with immense media scrutiny on Connolly's coaching, Fremantle again stormed home, winning a club record 9 games in a row and finished 3rd at the end of the home and away season. The finals series saw Fremantle lose to Adelaide away, before Connolly led them to the club's first ever win in finals game, against Melbourne at Subiaco Oval. The season ended the following week, with a loss to Sydney at Telstra Stadium in the preliminary final.
In 2007, in the final year of his contract, Connolly's future at Fremantle was constantly under scrutiny, as despite starting the season as one of the premiership favourites, the team performed poorly . Fremantle president Rick Hart publicly stated that making the finals will be a major factor in Connolly retaining the position. .On 18 July 2007, three days after Fremantle lost by four points to the Kangaroos at Subiaco Oval, Connolly announced that he would resign immediately. Connolly was given the chance to coach for two more games, but declined it. Assistant coach Mark Harvey coached fremantle for the remainder of the 2007 season in a caretaker role and was eventually employed full time.
Connolly is now the Melbourne Football Club football manager and an assistant coach.