Nach der Sinatra-Show kehrte Elvis nach Hollywood zurück, um seine Filmkarriere fortzusetzen, beginnend mit „G. I. Blues“ Ende April.
Einige Hintergrundaufnahmen für den Film wurden 1959 in Deutschland gedreht, als Produzent Hal Wallis Elvis besuchte, obwohl Elvis nicht an den Dreharbeiten teilnahm, da er seinen Militärdienst leistete. Die Hauptdarstellerin war Juliet Prowse, die zu dieser Zeit mit Frank Sinatra liiert war. Später behauptete Prowse, sie habe während der Dreharbeiten eine Affäre mit Elvis gehabt. Die beiden wurden nie öffentlich zusammen gesehen, wobei Prowse sagte, dass sie nie ausgehen würden, da Elvis von Fans belagert wurde. Prowse war damals vierundzwanzig und obwohl sie 1962 mit Sinatra verlobt war, hielt die Verlobung nicht lange.
In dem Film spielt Prowse die Nachtclubtänzerin Lili, die den Ruf hat, unnachgiebig gegenüber Verehrern zu sein. Als Elvis' Charakter, Tulsa McLean, unter Druck gesetzt wird, eine Wette einzugehen, sie zu daten und die Nacht mit ihr zu verbringen, wählt Tulsa den netten, sauberen, anständigen Ansatz. Er zieht sich jedoch von der Wette zurück, weil er sich unwohl fühlt und Lili wirklich mag. Eine Komplikation entsteht, als einer von Tulsas Mit-G.I.s erfährt, dass er aus einer früheren Begegnung Vater ist und sich eine Auszeit nimmt, um zu heiraten, wodurch Tulsa auf das Kind aufpassen muss. Das geht nicht gut aus und Tulsa muss Lili um Hilfe bitten. Die G.I.s, die die beiden im Auge behalten, denken, dass Tulsa die Wette infolgedessen gewonnen hat. Der Armeehauptmann erfährt jedoch von der Wette, und die Truppe gerät in große Schwierigkeiten, bis Lili das Baby in einer Garderobe bei seiner Mutter entdeckt, bevor die Militärshow stattfindet, für die sie probt.
Der Film enthält elf Songs, darunter eine Neuaufnahme von „Blue Suede Shoes“, die während einer frühen Bar-Schlägerei-Szene verwendet wird.
Elvis hasst die Songs und den Film und sagt, er habe sich dumm gefühlt, wenn er jedes Mal in Gesang ausbrach, wenn er sich an eine Frau heranmachte. Priscilla sagte, er rufe sie in Deutschland an und schimpfe über die Handlung und die Songs. Elvis kümmerte sich nicht um die leichten Familienunterhaltungs- oder romantischen Komödien-Genres. Trotzdem war der Film ein Riesenerfolg, ebenso wie das Soundtrack-Album, das „Elvis Is Back!“ problemlos übertraf und für zwei Grammys nominiert wurde: „Best Soundtrack Album“ und „Best Male Vocal“. Der Film wurde auch von der Writers Guild of America für „Best Written Musical“ nominiert.
Er war radikal leichter als sowohl „Jailhouse Rock“ als auch „King Creole“, aber rückblickend war das auch bei der Musik der Fall. Jerry Lee Lewis kommentierte die Musik der frühen 1960er Jahre vor der Beatles-Ära und sagte, sie sei „Bobby dies und Bobby das“ geworden, und bezog sich damit auf den poppigeren Sound von Leuten wie Bobby Darin und Bobby Vee.
Trotz seiner eigenen Vorbehalte entsprach der Erfolg des Films der Zeit; Rock 'n' Roll hatte sich beruhigt, zumindest vorübergehend.
Elvis war mit seinem nächsten Film „Flaming Star“, einem dramatischen Western, in dem er Pacer Burton spielt, viel glücklicher. Pacer ist der Sohn eines texanischen Ranchers und einer Kiowa-Mutter. Die Kiowa sind unzufrieden mit den zunehmenden Landansprüchen der texanischen Siedler und beginnen, verschiedene Ranches zu überfallen. Pacers Loyalität wird in Frage gestellt. Der Kiowa-Anführer Buffalo Horn garantiert die Sicherheit der Burtons, wenn Pacer mit den Kiowa reitet. Pacer hat einen Halbbruder, Clint (gespielt von Steve Forrest). Die Familie versucht, Neutralität zu wahren. Dies funktioniert für keine der beiden Seiten gut, und die Mit-Texaner wollen nichts mit den Burtons zu tun haben. Als Pacers Mutter Neddy verletzt wird, verzögern die Texaner den Arztbesuch. Als Neddy stirbt, gibt Pacer den Texanern die Schuld am Tod seiner Mutter und beschließt, mit den Kiowa zu reiten. Als Clint jedoch angegriffen wird, eilt Pacer ihm zu Hilfe und wird dabei tödlich verletzt. Pacer hat eine Vision des „flammenden Todessterns“ und reitet davon, um allein zu sterben.
Der Film war ursprünglich für Marlon Brando als Pacer und entweder Montgomery Clift oder Frank Sinatra als Clint geplant. Der Film hat nur zwei Lieder: das Titellied „Flaming Star“ und „A Cane and a High-Starched Collar“, das früh auf einer Familienfeier der Burtons aufgeführt wird.
Elvis erhält Lob für seine schauspielerische Leistung, und Quentin Tarantino, der zukünftige Regisseur des Films „Pulp Fiction“ von 1994, beschrieb „Flaming Star“ als „einen wirklich großartigen Western der 50er Jahre und vielleicht den brutalsten amerikanischen Western seiner Zeit.“
Obwohl der Film einen Gewinn abwarf, spielte „G.I. Blues“ etwa fünfmal so viel ein und hatte auch ein Soundtrack-Album, das die Charts in den USA und Großbritannien anführte und eine Nummer-1-Single in Großbritannien mit „Wooden Heart“ hervorbrachte.
Die finanziellen Zahlen sprachen Bände für Hal Wallis und Colonel Parker.
Der vergleichbare Erfolg von Elvis' nächsten beiden Filmen, „Wild in the Country“ und „Blue Hawaii“, würde dem von „G. I. Blues“ und „Flaming Star“ ähneln, wobei „Blue Hawaii“ sogar noch besser abschnitt als „G.I. Blues“. Dies besiegelte Elvis' Schicksal in Hollywood, und mit wenigen Ausnahmen gegen Ende seiner Zeit dort drehte Elvis familienfreundliche, romantische Musikkomödien, sehr zu seiner zunehmenden Frustration.
