Presley found himself in 1965 recording soundtrack albums for films that were almost a year away from release — gone were the days when the turnaround time from the final session for Elvis Is Back! to its arrival in the shops was less than one week. While working on this album, his most recent film in the theaters was Tickle Me, and Presley had completed three more movies since then. With titles like "A Dog's Life" and "Queenie Wahine's Papaya" he openly ridiculed the material, wasting time before finally approaching the microphone to do the job. He begrudgingly accepted songs given him that he would have rejected outright years earlier. He always finished the work, but in essence Presley had become a hired hand in his own career.
No singles were issued from songs on the album. Ten songs were recorded at the sessions for the soundtrack, but only nine were used in the film. The omitted song, "Sand Castles," was included on the album to bring the running order to ten tracks. Sales for the album were under 250,000, a new low for Presley's LP catalogue. The good news was the single issued in June 1966 two days before the album, the 1945 Victor Youngstandard "Love Letters" backed with Clyde McPhatter's 1958 rhythm and blues hit "Come What May". It made a respectable number 19 on the Billboard Hot 100, and at least reflected Presley's actual tastes away from obligations to the soundtrack recordings. It was also his first contemporary record release in three years since "(You're the) Devil in Disguise" in June 1963, arriving in stores less than two weeks after it was recorded.
In 2004 "Paradise, Hawaiian Style was reissued on the Follow That Dream label in a special edition that contained the original album tracks along with numerous alternate takes.