The song was first recorded by Crudup in Chicago on November 8, 1950, with Ransom Knowling on bass and Judge Riley on drums, and was released as a single on RCA Victor 22–0109.

[1] It gained further exposure in covers by Elvis Presley, who put his version on the B-side to his 1956 single "I Want You, I Need You, I Love You"; by Wanda Jackson who often shared the same bill as Presley; by Creedence Clearwater Revival, who recorded it as a track on their 1970 album, Cosmo's Factory; by Buffy Sainte-Marie on her 1972 album Moonshot; and by John Lennon (incorrectly titled "Since My Baby Left Me"), recorded during the Rock 'n' Roll sessions in 1973, but first released posthumously on Menlove Ave. in 1986.

"My Baby Left Me" was covered by the British rock band Slade in 1977 and released as a non-album single as a tribute to Elvis Presley, who died in August of that year.

The band's 1977 album Whatever Happened to Slade proved a commercial failure while their tour that spring had shown that they could no longer fill large venues.

[9] Upon its release, Tony Mitchell of Sounds picked "My Baby Left Me/That's Alright Mama" as "Best Comeback Single" and described it as a "fabulous treatment of this old Arthur Crudup number" which "could easily see Slade back in the charts".

He continued, "It's a bouncy, struttin' 12-bar blues quite unlike most of the band's earlier hit singles and it could just be the right thing to get them back into favour at the current time."