Although Kelly was raised as a Roman Catholic, he later described himself as a non-believer in any religion. He is the great great grandson of Jeremiah Kelly, who emigrated from Ireland in 1852 and settled in Clare, South Australia. His paternal grandfather, Francis Kelly, established a law firm in 1917, which his father, John, joined in 1937. John Kelly died in 1968 at the age of 52, after being diagnosed with Parkinson's disease three years earlier. Paul Kelly was thirteen years old when his father died. Kelly described his father: "I have good memories, he was the kind of father that, well, I missed him when he died very much. The older children were growing into him at the time he died. He was not well enough to play sport with me."