Kenna made his professional boxing debut in 1991 against Alvin 'Slick' Miller, where he was knocked down in the first round but rallied and stopped Miller on a third-round TKO. A nine-fight undefeated streak followed with eight wins and a draw. The fights in this streak were all against journeymen fighters until he fought Michael Sprott for the Southern Area Heavyweight Title. Colin was defeated for the first time in this fight with a first Round KO. Three successive wins followed before Kenna faced Audley Harrison's victim, Mark Krence, who at the time was highly rated and tipped as a future star. An injury to his elbow forced a corner retirement.
Two weeks later in his hometown of Dublin, Kenna had a draw with the journeyman Paul King. After a period of inactivity, in June 2005 he won a points victory over former British and Commonwealth champion Julius Francis. In his comeback fight, he fought Wayne Llewellyn for the Southern Area heavyweight title. Llewellyn had a 30–5 record including a victory over Michael Sprott and a defeat to world title challenger Jameel McCline. Kenna won the fight and became the new Southern Area heavyweight champion. Later, he fought in Germany against hotly tipped prospect Oleg Platov. The lack of training and preparation on Kenna's part showed and the referee stopped the fight in the fifth round.
After the fight in Germany, Kenna spent under a year out of the ring, contemplating retirement or becoming a journeyman fighter. He returned in February 2007 with a points victory against Keith Long, but has not won a fight since. Kenna has lost seven consecutive fights, the first of which came when he was out-pointed by undefeated Moldovan-born Israeli Roman Greenberg (27-0) over eight rounds in London on 31 October 2007. He was in trouble by the sixth round, and on the floor in seventh from a straight right hand. The only time Greenberg saw any trouble came when his stool collapsed under his sixteen and a half stone frame at the end of fifth round.
Kenna's defeats include losses to Sam Sexton and Albert Sosnowski, who went on to become the Commonwealth and European champions respectively. He also lost to undefeated Indian Gurcharan Singh. On 11 April 2008, Kenna appeared in the "Prizefighter" competition on Sky Sports, but was knocked out by Paul Butlin in 2nd round of the quarter final. In February 2010, Kenna fought for the Irish title against Coleman Barrett. Kenna managed to knock down Barrett in the second round but Barrett still won on points.
Kenna fought for the Southern Area title once more against Larry Olubamiwo in May 2010, but was knocked out in the first round.