The community's post office was established in 1854. The origin of the name is unclear, with some saying it honored postmaster John Donaldson's wife. It may also be a combination of "Ark" (possibly for the Winston County community) and "-adelphia" from Philadelphia. Notable early residents of the community included the family of Charles Drennen.
Brown & Hood, a dry goods business owned by two former clerks of Samuel Mudd's Elyton mercantile, opened in Arkadelphia in 1873. On March 27, 1875 the business burned to the ground, and reopened the following year in downtown Birmingham.
The section of U.S. Highway 78 called Arkadelphia Road in Birmingham is part of a now obscured road that once continued north to Arkadelphia. The Blount County road connecting Jefferson County Highway 89 at Warrior-Jasper Road and Cullman County Highway 35 at Mulberry Fork is also named Arkadelphia Road.
- Foscue, Virginia O. (1989) Place Names in Alabama. Tuscaloosa: University of Alabama Press. ISBN 081730410X