Per la canzone Handy disse di essersi ispirato a un incontro casuale nelle strade di St. Louis con una donna sconvolta dall'assenza del marito, che si lamentava ad alta voce dicendo: «Ma man's got a heart like a rock cast in de sea» ("Il mio uomo ha un cuore come un sasso gettato nel mare"), strofa chiave del brano.[1] I dettagli sulla storia sono variabili. Nella sua autobiografia, Handy raccontò di aver ascoltato per la prima volta la canzone a St. Louis nel 1892: "[il brano] aveva molte strofe di una sola frase e loro la cantavano tutta la notte" ("It had numerous one-line verses and they would sing it all night").
All'epoca della sua morte nel 1958, Handy percepiva royalties per circa 25,000 dollari all'anno per St. Louis Blues. Lo spartito originale della canzone è disponibile online presso la Biblioteca del Congresso degli Stati Uniti nel database relativo alla musica afroamericana della Brown University.[2]