Vanaf 1994 speelde hij bij Watford. Na een seizoen waar hij in 34 duels 15 maal scoorde verhuisde hij naar Feyenoord. Hij werd echter al snel uitgeleend aan de Britse voetbalclub Wolverhampton Wanderers en de Nederlandse voetbalclub Excelsior. Connolly was tijdens zijn tijd bij Excelsior de voetballer met het hoogste salaris van het Nederlandse voetbal dat jaar[1]. Van 2012 tot eind 2014 stond hij onder contract bij Portsmouth. Door die club werd hij tot aan het eind 2014 verhuurd aan Oxford United, uitkomend in de League Two van het Engelse profvoetbal. Vanaf januari 2015 speelt Connolly voor AFC Wimbledon. Op 8 maart 2015 zette hij een punt achter zijn loopbaan.[2]
Connolly kwam in totaal 41 keer uit voor de nationale ploeg van Ierland in de periode 1996-2004 en maakte 9 doelpunten. Hij maakte zijn debuut op woensdag 29 mei1996 in de vriendschappelijke thuiswedstrijd tegen Portugal (0-1). Hij moest in dat duel na 63 minuten plaatsmaken voor Keith O'Neill. Hij was ook aanwezig bij het WK voetbal 2002 in Japan en Zuid-Korea.