Leavelle was born and raised in Red River County, Texas. He served in the United States Navy during World War II, and was a sailor on board the USS "Whitney" during the December 7, 1941 Pearl Harbor bombings. 