Cleburne was born in Ovens, County Cork, Ireland, the second son of Dr. Joseph Cleburne, a middle-class physician of Anglo-Irish ancestry. Patrick's mother died when he was 18 months old, and he was an orphan at 15. He followed his father into the study of medicine, but failed his entrance exam to Trinity College of Medicine in 1846. In response to this failure, he enlisted in the 41st Regiment of Foot of the British Army, subsequently rising to the rank of corporal.