Con la firma del contrato de Elvis con la RCA, rápidamente la compañia no tardó en empezar a preparar la primera sesión de grabación de Elvis. La RCA tenía las canciones que había adquirido del sello SUN, las cuales re-editaría, ya con el nuevo sello, para ganar tiempo mientras Elvis grababa nuevos temas para poder sacar un single y comenzar a recuperar la inversón realizada en su nuevo artísta. Como a primeros de 1956, Elvis todavía tenía unos compromisos de giras ya pactadas, se acordó que la primera sesión tendría lugar en Nashville el dia 10 de enero, y de paso permitía a Elvis poder celebrar el día 8 su 21º cumpleaños.
El 10 de enero de 1956, dos días después de su vigésimo primer cumpleaños, Elvis tiene su primera sesión de grabación para el sello RCA, que tuvo lugar en su estudio en Nashville. Entre los temas previstos en la cinta durante este período de sesiones se encontraba "Heartbreak Hotel". El primer single con RCA, "Heartbreak Hotel"/"I Was The One" sale al mercado y vende más de 300.000 copias en sus primeras tres semanas. Pronto se convertiría en número 1 en el Billboard de singles. durante ocho semanas y también #1 en las listas country, y #5 en el chart R & B. Se convierte en el primer single de Elvis en vender más de un millón de copias, otorgándole su primer disco de oro el 27 de enero de 1956. Elvis aparece con Scotty, Bill y DJ bajo la producción de Jackie Gleason en el programa "Stage Show" el 28 de enero de 1956, protagonizada por Tommy y Jimmy Dorsey, en la cadena de televisión CBS. Esta es la primera aparición de Elvis en televisión. Aparecerá cinco noches más en el "Stage Show" en las próximas semanas. La última de estas seis apariciones será el 24 de marzo. Paralelamente, los viajes y los conciertos continúan durante este tiempo, incluidas las apariciones en el "Louisiana Hayride", apariciones que todavía tiene que hacer dado que está bajo contrato.