Leary's father was a free born African-American harnessmaker. Lewis Leary was born at Fayetteville, North Carolina. His paternal grandparents were an Irishman, Jeremiah O'Leary, who fought in the American Revolution under General Nathanael Greene, and his wife of African, European and Native American descent. His great grandfather, Aaron Revels, also fought in the revolution. Through Revels, he was a cousin to Hiram Rhodes Revels, the first African-American to serve in the United States Senate. His brother was North Carolina politician and lawyer, John S. Leary