Après le spectacle de Sinatra, Elvis est retourné à Hollywood pour reprendre sa carrière cinématographique, en commençant par « G. I. Blues » fin avril.
Certaines images de fond pour le film ont été tournées en Allemagne en 1959, lorsque le producteur Hal Wallis a rendu visite à Elvis, bien qu'Elvis n'ait pas participé au tournage, conformément à son service militaire. La première dame était Juliet Prowse, qui sortait avec Frank Sinatra à l'époque. Plus tard, Prowse dirait qu'elle a eu une liaison avec Elvis pendant le tournage. Les deux n'ont jamais été vus ensemble en public, Prowse disant qu'ils ne sortiraient jamais car Elvis était harcelé par ses fans. Prowse avait vingt-quatre ans à l'époque, et bien qu'elle se soit fiancée à Sinatra en 1962, les fiançailles n'ont pas duré.
Dans le film, Prowse joue Lili, une danseuse de boîte de nuit, qui a la réputation d'être impitoyable envers ses admirateurs. Lorsque le personnage d'Elvis, Tulsa McLean, est enrôlé de force pour parier sur elle et passer la nuit avec elle, Tulsa adopte une approche gentille, propre et saine. Cependant, il renonce au pari parce qu'il n'est pas à l'aise et qu'il aime sincèrement Lili. Une complication survient lorsqu'un des camarades G.I. de Tulsa découvre qu'il est père d'une précédente rencontre et prend un congé pour se marier, laissant Tulsa à la garde d'enfants. Cela ne se passe pas bien, et Tulsa doit faire appel à Lili pour obtenir de l'aide. Les G.I. qui les surveillent pensent que Tulsa a gagné le pari en conséquence. Cependant, le capitaine de l'armée découvre le pari, et l'équipe est en grands ennuis jusqu'à ce que Lili repère le bébé dans une loge avec sa mère avant le spectacle des forces armées, pour lequel elle répète.
Le film contient onze chansons, dont un remake de « Blue Suede Shoes », utilisé lors d'une scène de bagarre dans un bar.
Elvis déteste les chansons et le film, disant qu'il se sentait stupide à chanter chaque fois qu'il faisait une approche avec une fille. Priscilla a dit qu'il l'appelait en Allemagne et se plaignait de l'intrigue et des chansons. Elvis n'aimait pas les genres de divertissement léger, familial ou de comédie romantique. Malgré cela, le film a été un énorme succès, tout comme l'album de la bande originale, qui s'est vendu plus que « Elvis Is Back ! » et a été nominé pour deux Grammys, « Meilleur album de bande originale » et « Meilleure performance vocale masculine ». Le film a également été nominé par la Writers Guild of America pour « Meilleure comédie musicale écrite ».
Il était radicalement plus léger que « Jailhouse Rock » et « King Creole », mais avec le recul, il en allait de même pour la musique. Jerry Lee Lewis commenterait la musique du début des années 1960, avant l'ère des Beatles, disant qu'elle était devenue « Bobby ceci et Bobby cela », faisant référence au son plus pop de personnalités comme Bobby Darin et Bobby Vee.
Malgré ses propres réserves, le succès du film était conforme à l'époque ; le rock 'n' roll s'était calmé, du moins temporairement.
Elvis fut beaucoup plus heureux avec son film suivant, « La Chevauchée vers l’Ouest » (Flaming Star), un western dramatique dans lequel il joue Pacer Burton. Pacer est le fils d’un éleveur texan et d’une mère Kiowa native. Les Kiowas sont mécontents des revendications croissantes des colons texans sur leurs terres et commencent à attaquer divers ranchs. La loyauté de Pacer est mise en doute. Le chef Kiowa, Buffalo Horn, garantira la sécurité des Burton si Pacer chevauche avec les Kiowas. Pacer a un demi-frère, Clint (joué par Steve Forrest). La famille essaie de maintenir sa neutralité. Cela ne fonctionne pas bien pour aucun des deux camps, et les Texans ne veulent rien avoir à faire avec les Burton. Lorsque la mère de Pacer, Neddy, est blessée, les Texans empêchent le médecin de la soigner. Lorsque Neddy meurt, Pacer blâme les Texans pour la mort de sa mère et choisit de chevaucher avec les Kiowas. Cependant, lorsque Clint est attaqué, Pacer vient à son secours et est mortellement blessé en conséquence. Pacer a une vision de « l’étoile enflammée de la mort » et s’en va mourir seul.
Le film avait été initialement prévu pour que Marlon Brando joue Pacer et soit Montgomery Clift ou Frank Sinatra pour jouer Clint. Le film ne contient que deux chansons : la chanson titre « Flaming Star » et « A Cane and a High-Starched Collar » interprétée au début lors d’une fête de la famille Burton.
Elvis reçoit des éloges pour son jeu d’acteur, et Quentin Tarantino, le futur réalisateur du film « Pulp Fiction » de 1994, a décrit « Flaming Star » comme « un western des années 50 vraiment génial, et peut-être le western américain le plus brutalement violent de son époque ».
Cependant, bien que le film ait été rentable, « G.I. Blues » a rapporté environ cinq fois plus, et il avait également une bande originale qui a atteint le sommet des classements aux États-Unis et au Royaume-Uni et a donné lieu à un single numéro 1 au Royaume-Uni avec « Wooden Heart ».
Les chiffres financiers en disaient long à Hal Wallis et au Colonel Parker.
Le succès comparatif des deux films suivants d’Elvis, « Wild in the Country » et « Blue Hawaii », refléterait celui de « G. I. Blues » et « Flaming Star », « Blue Hawaii » étant encore plus performant que « G.I. Blues ». Cela scella le destin d’Elvis à Hollywood et, à quelques exceptions près vers la fin de son séjour, Elvis ferait des comédies musicales romantiques et familiales, à sa frustration croissante.
