Born in Barnet, London, Connolly started his career as a youth at Arsenal, eventually making the reserve side. In September 2006 he was made captain of Arsenal's reserves. He made his first-team debut for Arsenal on 24 October 2006, starting a League Cup third round match against West Bromwich Albion. On 23 November 2006 Arsenal announced he was going on loan to Bournemouth until 2 January 2007. In total he played seven games for Bournemouth, and scored his first goal at senior level in a 2–0 win over Nottingham Forest, on 5 December 2006. He returned to Arsenal as scheduled at the start of January 2007, and came on as a substitute for Armand Traoré against Liverpool in the League Cup Quarter-finals on 9 January. On 9 July 2007 Arsenal announced he would be spending the whole of the 2007–08 season on loan to Colchester United, although he eventually was recalled midway through the loan on 2 January 2008.
The same day, his transfer to Queens Park Rangers was announced, after a lack of first-team opportunities were offered by Arsenal. His debut came on 5 January, in a 1–0 loss to Chelsea in the FA Cup. He scored his first goal for QPR against Blackpool on 16 January 2010. In the meantime, in November, he received his first call-up to the England U-21 squad, where he joined Arsenal teammate Theo Walcott. His second goal came on 6 March against West Bromwich Albion in a 3–1 win. During the 2010–11 season, Connolly played a part in QPR's Championship title win playing 36 out of 43 games. He joined Reading on a loan on 31 January 2012 until the end of the 2011–12 season. He made his debut on 11 February 2012 in a 2–0 win against Coventry City. He only played 6 times during Reading's promotion push which resulted in Reading winning the Championship title.
Cardiff City
On 20 August 2012, QPR had accepted a £500,000 bid from Cardiff City for Connolly's services. On 22 August, the deal was completed and Connolly signed a contract that would keep him at the Cardiff City Stadium for 3 years. He made his debut in the Severnside derby against Bristol City on 25 August. He scored his first and second goal for the club in a 3–0 win over Blackpool on 29 September. His third goal came a month later against Burnley, and later scored his fourth against Middlesbrough. Making thirty-six appearances and scoring five goals, Connolly was a key figure as Cardiff won the Championship title, the third time in successive seasons that Connolly has achieved the feat. He started the Premier League season playing at right back until new signing Kevin Theophile-Catherine became a permanent fixture in the side. Cardiff were relegated after just one season in the top flight. Connolly had then returned to the starting eleven partnering Mark Hudson in a 1–1 draw at Blackburn Rovers. On 19 March 2015 Connolly joined another Championship side, Watford, on loan until the end of the 2014–15 season, despite having played 26 times for Cardiff that season. Manager Russell Slade stated the deal was a business rather than a footballing decision, with Connolly expressing his surprise at the move. Whilst at Watford, Connolly achieved the feat of being promoted to the Premier League for the fourth time with four different clubs. At Watford Connolly scored once; in a 3–1 win at Nottingham Forest. Connolly rejoined the Cardiff squad for the 2015–16 season, earning himself a permanent place in the side alongside Sean Morrison. He had become of interest to other clubs during the January transfer window, due to his impressive performances that season. These feats thus earned him a contract extension till 2019 and also the club's Player of the Year award. He was released by Cardiff at the end of the 2019-20 season.
