Originally recorded in Nashville in 1959 by Lefty Frizzell and produced by Don Law, it reached #6 on the U.S. Country chart. The song was written by composer and singer Danny Dill with Marijohn Wilkin in a folk music style in 1959. Wilkin also played piano on the original recording by Frizzell.

The writers later stated that they drew on three sources for their inspiration: Red Foley's recording of "God Walks These Hills With Me"; a contemporary newspaper report about the unsolved murder of a priest; and the legend of a mysterious veiled woman who regularly visited Rudolph Valentino's grave. Dill himself called it an "instant folksong".