The O'Kelly sept of Uí Maine is descended from Cellach mac Fíonachta, who lived in the 9th century.

The first to bear the surname was Tadhg Mór Ó Ceallaigh,[7] a grandson of the former who was slain in the Battle of Clontarf fighting on behest of his ally Brian Boru, king of Munster and high king of Ireland.

According to historian C. Thomas Cairney, the O'Kellys came from the tribe of Ui Maine who in turn were from the Dumnonii or Laigin who were the third wave of Celts to settle in Ireland during the first century BC.

[6] The earliest parts of the O'Kelly genealogy are contained in the Book of Hy Many, which was written in the latter half of the 14th century on behest of the then archbishop of Tuam, Muircheartach mac Pilib Ó Ceallaigh.

[9] The O'Kelly sept of Cualu is descended from Cellach Cualann mac Gerthidi,[10] an Uí Máil king of Leinster in the late 7th through to the early 8th century.