The song is generally credited as being written by Hedy West, and a 1961 copyright is held by Atzal Music, Inc. "500 Miles" is West's "most anthologized song." Some recordings have also credited Curly Williams, and/or John Phillips as co-writers. David Neale writes that "500 Miles" may be related to the older folk song, "900 Miles", which may itself have origins in the southern American fiddle tunes "Reuben's Train" and "Train 45".
The song appears on the 1961 self-titled debut album by The Journeymen; this may have been its first release.
Rewritten with new lyrics (by Bobby Bare), it charted as a hit single by American country music singer Bobby Bare in 1963 (#10 US, #7 NOR, #9 SWE, #16 DEN). Bare's version features a spoken recitation following the repeat of the refrain, before he sings one original line of his second verse. Following this, he makes a transition from the key of G to the key of D for the third verse, featuring a counterpoint portion by the backup singers, before making a transition back to the key of G for the last refrain, before the song's fade. The lyrics feature heavily in the Bob Dylan song "I Was Young When I Left Home".
The Hooters recorded a version of this song with additional lyrics, dedicated to the Tiananmen Square protests of 1989. It goes: "A hundred tanks along the square, one man stands and stops them there. Some day soon, the tide will turn, and I'll be free".