Leonidas Fleming was probably born in the mid-1840s. By the early 1860s, he was probably living in Texas. He enlisted in the Confederate army in June 1861, and he mustered in as a bugler in Company C of the 2nd Texas Cavalry. He apparently lied about his age, claiming that he was 18 years old. In July 1862, he and comrade Alonzo Russell swore that they were “under the age of 18 years and entitled to our discharges.” His service records, however, show that he “reenlisted” in the regiment in August 1862. He was discharged in late 1863.