Newspaper reports in October 2001 claimed Kelly had joined Third Division side Carlisle United, which were denied by Derry, who had rejected Carlisle's £100,000 bid for him. He featured for Derry in the League of Ireland Cup Final in April 2002, and scored in the penalty shoot-out, which the team lost 3–2. He eventually became one of many League of Ireland players who joined Carlisle under the management of Roddy Collins in August 2002 for a fee believed to be around £100,000. He made his Carlisle debut in a 2–0 defeat to Darlington on 27 August. He featured for Carlisle in the 2003 Football League Trophy Final on 6 April 2003, which they lost 2–0 to Bristol City. His first goal for Carlisle came as the equaliser in a 1–1 draw against York City and he finished the 2002–03 season with 42 appearances. Following the end of the 2003–04 season, Carlisle manager Paul Simpson told Kelly he needed to get fit if he wanted to stay at the club.