Presley se encontró en 1965 grabando bandas sonoras para películas a estrenar un año después, en contraposición con grabaciones como Elvis Is Back! donde el tiempo entre la última sesión y la publicación del álbum era menos de una semana.[3] Mientras trabajaba en Paradise, Hawaiian Style, su película más reciente en los teatros era Tickle Me, y Presley había completado otras tres películas desde entonces.
Ningún sencillo fue extraído del álbum. Diez canciones fueron grabadas en las sesiones de Paradise, Hawaiian Style, pero solo nueve fueron incluídas en el largometraje. «Sand Castles», la canción omitida, fue incluída en la banda sonora para aumentar la duracción del álbum. Las ventas del álbum fueron inferiores a las 250 000 unidades, un nuevo bajón con respecto a trabajos anteriores de Presley.[4] A pesar del decreciente interés en su carrera musical, con el auge de nuevos artistas como The Beatles, Presley consiguió obtener un puesto diecinueve con el sencillo «Love Letters», publicado en junio de 1966.[5]