I 1965 spelte Presley inn musikk for filmar, nesten eitt år før filmane kom ut. Borte var dagane då det kunne ta mindre enn ei veke frå Presley var i studio, til plata var på plass i butikkane, slik det t.d. var for Elvis Is Back!.[3] Medan han arbeidde på dette albumet gjekk den siste filmen hans, Tickle Me på kino, og Presley hadde fullført tre filmar til sidan den gongen. Med titlar som «A Dog's Life» og «Queenie Wahine's Papaya» gjorde han ope narr av songane han spelte inn, og sløste med tida før han kom bort til mikrofonen for å syngje.[4] Han aksepterte motvillig songane han vart tilbode, og som han kjapt ville ha avvist i tidlegare år. Han fullførte alltid arbeidet, men i røynda hadde Presley vorte ei leigehjelp i sin eigen karriere.[4]
Det vart ikkje gjeve ut singlar frå albumet. Det vart spelt inn ti songar i innspelinga for filmen, men berre ni vart nytta i filmen. Den siste songen, «Sand Castles», vart med på albumet for at talet skulle kome opp i ti songar. Salet for albumet var under 250 000, ein ny botnrekord for eit Presley-album.[5] Den gode meldinga var singelen som kom ut i juni 1966, to dagar før albumet, standarden «Love Letters» i lag med Clyde McPhatter sin rhythm and blues-hit «Come What May». Denne nådde respektable 19. plassen på Billboard Hot 100, og reflekterte i det minste den faktiske musikksmaken til Presley.[6] Det var òg den første nyare innspelinga som kom ut på tre år sidan «(You're the) Devil in Disguise» i juni 1963, og kom i butikkane mindre enn to veker etter han vart spelt inn.[7]
I 2004 vart Paradise, Hawaiian Style gjeve ut på ny på Follow That Dream i ei spesialutgåve med originalalbumet og fleire alternative opptak.[8]
