Twelve songs were recorded at the sessions for Frankie and Johnny, and all were used and issued on the soundtrack. The title song was issued as a single, with "Please Don't Stop Loving Me" on the b-side. Released either just before or simultaneously with the album, depending if the disputed release dates are correct, "Frankie and Johnny" peaked at number 25 on the Billboard Hot 100, with the b-side also charting at number 45.
During the 1970s, Pickwick Records had leased several of Presley's recordings from RCA and reissued the soundtrack album in 1976 with a new cover showing a 1970s-era image of Presley and the title slightly amended to Frankie & Johnny. The running order of the tracks was altered and three songs from the original album were omitted —"Chesay", "Look Out Broadway", and "Everybody Come Aboard". The front cover does not indicate that this is a reissued soundtrack album, and it was the only soundtrack to be reissued in this way. It did not chart on the Billboard 200. This oddity remained in print for several years and when, following Presley's death in August of 1977, RCA reissued all of his albums, the agreement between RCA and Pickwick prohibited RCA from reissuing the original, complete soundtrack album in the US for several years due to the existence of this version. The original Frankie and Johnny soundtrack album was reissued in Canada and elsewhere however. Not until 2010 would the complete original Frankie and Johnny soundtrack be widely available in the United States again.
In 2003 Frankie and Johnny was reissued on the Follow That Dream label in a special edition that contained the original album tracks along with numerous alternate takes.
"Frankie and Johnny" was released as a single (RCA 8780) in March 1966 and appeared on Billboard's Hot 100 list for eight weeks. Its highest position was number 25. The single's B-side, "Please Don't Stop Loving Me", also charted for eight weeks and reached number 45.