Kelly was born in Belfast, in the nationalist Lower Falls neighborhood. In the late 1960s, he became active in the civil rights movement, but he became disillusioned with peaceful methods of resolving issues in Northern Ireland, and by 1972 had joined the IRA.
In 1973, a referendum was held in Northern Ireland to assess whether its citizens wished to remain part of the United Kingdom; the referendum was largely boycotted by the nationalist community. In response to the referendum, the IRA sent the 19-year-old Kelly and eight others to set off four car bombs in London. While two of the bombs were defused, one at the Old Bailey and another at Scotland Yard exploded, killing one person and injuring nearly 200. Kelly was convicted of causing explosions and conspiracy to cause explosions and given two life sentences plus 20 years.
In prison, Kelly and his partners were treated as ordinary criminals, and went on hunger strike seeking recognition as political prisoners and to be transferred to a prison in Northern Ireland. The prison authorities chose to force feed hunger strikers at this time; Kelly was force fed 170 times during a 205 day hunger strike. In 1975 he was transferred to Long Kesh prison in Northern Ireland. In September 1983, Kelly and 37 other IRA prisoners broke out of Long Kesh by stealing a food truck. During the escape Kelly shot a prison guard who attempted to stop the prisoners.
After escaping from prison Kelly was involved in IRA activities in Europe. He was rearrested in Amsterdam in 1986 and extradited to Northern Ireland, returning to Long Kesh. He was released from prison in 1989.
After his release Kelly became active in politics as a member of Sinn Féin. Kelly played an important role in the negotiations with the British government that led to the Good Friday Agreement in 1998. In 1998 he was also elected to the Northern Ireland Assembly. Kelly is Sinn Féin's spokesperson for policing and justice