En enero de 1958 y una vez acabadas las fiestas navideñas y celebrado su 23º aniversario, Elvis abandona Memphis en dirección a California donde empieza la filmación de su cuarta película, una adaptación de la novela "A Stone For Danny Fisher". Es la segunda película para la Paramount Pictures, bajo la producción de Hal B. Wallis. En esta ocasion la dirección del film corre a cargo del veterano director Michael Curtiz que años antes había dirigido la película "Casablanca". Ambientada en New Orleans, el reparto, incluye al actor Walter Matthau, Dean Jagger, Carolyn Jones y nuevamente Dolores Heart (Loving You). La película quizás sea la más consistente en cuanto a guión. La misma calidad tendrá también la banda sonora (grabada en los Radio Recorders), que nuevamente cuenta con una buena selección de temas entre los que destacan nuevas composiciones de sus admirados Jerry Leiber & Mike Stone. Después de barajar varios títulos, la película se titulará King Creole y estará considerada por muchos como su mejor interpretación en la gran pantalla.
Finalizados sus compromisos cinematográficos, el 24 de marzo, Elvis Presley es admitido en el Ejército de los EE.UU. Se le asigna el número de serie 53310761. El 25 de abril se le hace a Elvis el famoso corte de pelo, en Fort Chaffee, Arkansas. Cuatro días más tarde, el 28 de marzo, Elvis llega a Fort Hood, Texas, para la formación básica y se encuentra estacionado allí durante seis meses. Para poder dejar nuevo material grabado que pueda ser publicado durante su ausencia, gracias a un breve permiso del ejército,se prepara una mini sesión de una noche en Nashville en el nuevo Studio B, donde dejará grabadas 5 canciones que a excepción de una todas serán publicadas durante su servicio militar. Por primera vez, para esta sesión en el estudio no se encuentran Scotty Moore ni Bill Black con los que mantiene diferencias económicas. Scotty volveria a tocar con Elvis en los 60's pero Bill Black ya no volvería, iniciando su própia carrera con su banda "Bill Black Combo". Estas ausencias son cubiertas por Chet Atkins, Hank Garland y Bob Moore a los que se añade un nuevo batería (que acompañará a D.J.Fontana) como Buddy Harman y el pianista Floyd Cramer. Será la última sesión de grabación de Elvis en los 50's. Con su ingreso en el ejército, se cierra la primera etapa de la carrera de Elvis, la etapa del Rock & Roll. Para su vuelta, todo habría cambiado, nada volvería a ser igual.