The song was Gunter's first recording, made at Huel Murphy's home studio with "The Pebbles", former colleagues from the Golden River Boys. The tune, which showcases the individual musicians, was popular on tour and was re-recorded at WBRC-AM prior to being released, with "How Can I Believe You Love Me." on the flip side. The single is sometimes considered to be the first rock and roll record ever produced, beating Sam Phillips' "Rocket 88" by over a year.
The song was a regional hit and led to a highly-successful tour. In some cases the shows were relocated to airport hangers to accommodate the large crowds. After Bama's Manny Pearson turned down offers from Decca Records' Paul Cohen to re-release the master, Decca chose instead to issue a cover by country singer Red Foley. That release quickly climbed the national charts, sitting at number one on the country charts for 14 weeks. The presence of a hotter-selling version led stores to send back Gunter's earlier release.
"Birmingham Bounce" was later covered by Lionel Hampton, Tommy Dorsey, Amos Milburn, Pee Wee King, Tex Williams and others. Gunter followed "Birmingham Bounce" with "(Gonna Rock and Roll) Gonna Dance All Night", one of the first tunes with the words "rock and roll" in the lyric.