El 1 de febrero de 1956, mientras "Heartbreak Hotel" hace su escalada en las listas de éxitos en su camino al número #1, el single "I Forgot To Remember To Forget"/"Mystery Train", que representa su quinto y último single bajo la etiqueta de Sun Records, llegará al #1 en la lista nacional Country Billboard. Su primer hit #1 en una lista nacional de éxitos. El 23 de marzo de 1956 RCA saca a la luz "Elvis Presley", el primer álbum de Elvis. El disco pronto va al número # 1 en lista Billboard de álbumes pop por espacio de 10 semanas. Es el primer álbum de Elvis que llega a más de $ 1 millón en ventas, ganando así su primer LP de oro.
El 26 de marzo de 1956 Elvis llega a Los Ángeles para comenzar una prueba de pantalla para los estudios Paramount en Hollywood el 26 y 27. La prueba constará de dos partes, una en la que debe interpretar "Blue Suede Shoes" y en la segunda la realización dos escenas de la película aún sin estrenar, y que llevaba por título "The Rainmaker". Esta película en un principio tenía como protagonistas principales Burt Lancaster y Katharine Hepburn. El productor Hal B. Wallis queda convencido de las posibilidades de Elvis como actor, de forma que negocia con el Col.Tom Parker los términos del contrato de Elvis com Paramount Pictures.