Publicado en marzo de 1966, el LP Frankie And Johnny era una nueva banda sonora para la película que Elvis realizó para la United Artist pictures. Las sesiones de grabación tuvieron lugar en los Radio Recorders de Hollywood, con Elvis no asistiendo a las grabaciones principales y añadiendo su parte vocal posteriormente en los mismos Radio Recorders o en los Goldwyn Studios. A destacar Hard Luck, Please Don't Stop Loving Me o What Every Woman Lives For, pero por desgracia, el material una vez más no era lo suficientemente bueno como para sentirse motivado o lo más importante, competir con la creatividad y calidad de las grabaciones de ésa época. Ya a finales de 1965, las ventas de discos de Elvis habían bajado un 40% aproximadamente...este hecho no pasó desapercibido en los despachos de RCA. Fue a partir de 1966 que las cosas empezaron a preocupar no sólo a Elvis...sino al propio Coronel Parker. Frankie And Johnny llegó al puesto número 20 de las listas Billboard y sus ventas no superaron las 300.000 cópias. En la actualidad este LP esta catalogado como disco de platino por la RIAA.