Después del espectáculo de Sinatra, Elvis regresó a Hollywood para reanudar su carrera cinematográfica, comenzando con "G. I. Blues" a finales de abril.
Algunas escenas de fondo para la película se rodaron en Alemania en 1959, cuando el productor Hal Wallis visitó a Elvis, aunque Elvis no participó en ninguna de las filmaciones, en consonancia con su servicio militar. La protagonista femenina era Juliet Prowse, que salía con Frank Sinatra en ese momento. Más tarde, Prowse diría que tuvo un romance con Elvis durante el rodaje. Nunca se les vio juntos en público, y Prowse decía que nunca saldrían porque Elvis estaba acosado por sus fans. Prowse tenía veinticuatro años en ese momento y, aunque se comprometió con Sinatra en 1962, el compromiso no duró.
En la película, Prowse interpreta a Lili, una bailarina de club nocturno, que tiene fama de ser implacable con sus admiradores. Cuando el personaje de Elvis, Tulsa McLean, es obligado a aceptar una apuesta para salir con ella y pasar la noche, Tulsa adopta un enfoque amable, limpio y saludable. Sin embargo, se retira de la apuesta porque no se siente cómodo y le gusta genuinamente Lili. Surge una complicación cuando uno de los compañeros de G.I. de Tulsa descubre que es padre de un encuentro anterior y se toma un tiempo libre para casarse, dejando a Tulsa a cargo del bebé. Esto no sale bien y Tulsa debe pedir ayuda a Lili. Los G.I. que los vigilan piensan que Tulsa ha ganado la apuesta como resultado. Sin embargo, el Capitán del ejército se entera de la apuesta, y el grupo está en serios problemas hasta que Lili ve al bebé en un camerino con su madre antes del espectáculo de las fuerzas armadas, para el cual está ensayando.
La película contiene once canciones, incluido un remake de "Blue Suede Shoes", utilizado durante una escena temprana de pelea en un bar.
Elvis odia las canciones y la película, diciendo que se sentía estúpido irrumpiendo en canciones cada vez que intentaba ligar con una chica. Priscilla dijo que la llamaba a Alemania y se quejaba de la trama y las canciones. A Elvis no le importaban los géneros de entretenimiento ligero, familiar o comedia romántica. A pesar de esto, la película fue un gran éxito y también lo fue el álbum de la banda sonora, que superó cómodamente a "Elvis Is Back!" y fue nominado a dos Grammys, "Mejor Banda Sonora" y "Mejor Vocalista Masculino". La película también fue nominada por el Sindicato de Guionistas de América a "Mejor Musical Escrito".
Fue radicalmente más ligera que "Jailhouse Rock" y "King Creole", pero mirando hacia atrás en el tiempo, lo mismo ocurría con la música. Jerry Lee Lewis comentaría sobre la música de principios de la década de 1960, la era pre-Beatles, diciendo que se había convertido en "Bobby esto y Bobby aquello", refiriéndose al sonido más pop de artistas como Bobby Darin y Bobby Vee.
A pesar de sus propias reservas, el éxito de la película estaba en consonancia con la época; el rock 'n' roll se había calmado, al menos temporalmente.
Elvis estuvo mucho más feliz con su siguiente película, “Flaming Star”, un western dramático en el que interpreta a Pacer Burton. Pacer es el hijo de un ranchero texano y una madre nativa Kiowa. Los Kiowa no están contentos con las crecientes reclamaciones de tierras de los colonos texanos y comienzan a asaltar varios ranchos. La lealtad de Pacer se pone en duda. El líder Kiowa, Buffalo Horn, garantizará la seguridad de los Burton si Pacer cabalga con los Kiowa. Pacer tiene un medio hermano, Clint (interpretado por Steve Forrest). La familia intenta mantener la neutralidad. Esto no funciona bien para ninguna de las partes, y los propios texanos no quieren tener nada que ver con los Burton. Cuando la madre de Pacer, Neddy, resulta herida, los texanos impiden que el médico la atienda. Cuando Neddy muere, Pacer culpa a los texanos de la muerte de su madre y elige cabalgar con los Kiowa. Sin embargo, cuando Clint es atacado, Pacer acude en su ayuda y resulta herido de muerte como resultado. Pacer tiene una visión de la “estrella de fuego de la muerte” y se marcha para morir solo.
La película se había planeado originalmente para que Marlon Brando interpretara a Pacer y Montgomery Clift o Frank Sinatra a Clint. La película solo tiene dos canciones: la canción principal “Flaming Star” y “A Cane and a High-Starched Collar” interpretada al principio en una fiesta de la familia Burton.
Elvis recibe elogios por su actuación, y Quentin Tarantino, el futuro director de la película de 1994 “Pulp Fiction”, describió “Flaming Star” como “un western verdaderamente genial de los años 50, y quizás el western estadounidense más brutalmente violento de su época”.
Sin embargo, aunque la película obtuvo beneficios, “G.I. Blues” recaudó unas cinco veces más, y además tuvo un álbum de banda sonora que encabezó las listas en EE. UU. y el Reino Unido y produjo un sencillo número 1 en el Reino Unido con “Wooden Heart”.
Las cifras financieras hablaron por sí solas a Hal Wallis y al Coronel Parker.
El éxito comparativo de las dos siguientes películas de Elvis, “Wild in the Country” y “Blue Hawaii”, reflejaría el de “G. I. Blues” y “Flaming Star”, siendo “Blue Hawaii” incluso mejor que “G.I. Blues”. Esto selló el destino de Elvis en Hollywood y, con algunas excepciones hacia el final de su estancia allí, Elvis haría comedias musicales románticas y orientadas a la familia, para su creciente frustración.
