At 17 years of age Connolly appeared in St. Helens' ill-fated defeat to their arch rivals at Wembley in 1989 on the back of some impressive performances. He was selected to go on the 1992 Great Britain Lions tour of Australia and New Zealand. His move to rivals, Wigan, in 1993 was a controversial one and many St. Helens followers labelled him 'Judas'. Wigan paid £250,000 for Gary Connolly when he moved from St Helens in 1993 (based on increases in average earnings, this would be approximately £451,000 in 2009).
Connolly was regarded as one of the premier British centres of his generation and appeared 31 times for the national side excelling in the defensive side of the game, although his try scoring record was very modest at this level.