Innerhalb von 18 Monaten veröffentlichte Sun Records fünf Elvis-Singles. Die erfolgreichste davon war die Kombination aus „I Forgot to Remember to Forget“ und „Mystery Train“, die letzte Single, aufgenommen 1955 und die im Februar 1956 die US Country Chart anführte. Es war Elvis' erste Nummer-eins-Single in einer nationalen Hitparade.
Zu diesem Zeitpunkt war Elvis bereits von Colonel Tom Parker, einem Promoter von Country-Show-Paketen mit Hank Snow, unter Vertrag genommen worden. Colonel Parker hatte Elvis seinen Shows vorgestellt, und nachdem er gesehen hatte, wie Elvis alle etablierten Country-Künstler der damaligen Zeit in den Schatten stellte, als er die Bühne betrat, beschloss Parker, Elvis einen exklusiven Managementvertrag anzubieten. Elvis unterschrieb den Vertrag mit Colonel Parker am 15. August 1955 mit Zustimmung seiner Eltern, da er noch keine einundzwanzig war. Vernon ließ sich leicht überreden, aber Gladys brauchte einige Zeit, um zuzustimmen, da sie dem Colonel nicht ganz vertraute.
Colonel Parker hatte RCA Victor im Visier und half bei den Verhandlungen mit ihnen, um eine Rekordsumme von 35.000 US-Dollar an Sun Records zu zahlen. Obwohl Elvis zögerte, Sam zu verlassen, hatte Sun Records nicht die Kapazität, die Nachfrage nach Elvis-Platten zu befriedigen oder sie international zu vertreiben. Sam erklärte später, dass er so lange finanziell gekämpft hatte, dass er, als sich die Gelegenheit bot, einen Preis festlegte, von dem er nicht glaubte, dass er akzeptiert würde, was ihm erlauben würde, Elvis zu behalten. Als RCA jedoch akzeptierte, war Sam nicht in der Lage, abzulehnen. Der Deal brachte Elvis auch einen Bonus von 5.000 US-Dollar ein. Heute würde der Deal rund 500.000 US-Dollar betragen. Der Vertrag zwischen RCA, Sun und Elvis wurde am 20. November 1955 unterzeichnet, wobei Sam Elvis riet: „Lass dir von niemandem sagen, was du tun sollst, verliere deine Individualität nicht.“ Sam Phillips sollte später die Karrieren von Johnny Cash, Carl Perkins, Jerry Lee Lewis und Roy Orbison starten. Sam und Elvis blieben Freunde. Bei einem Besuch im Studio am 4. Dezember 1956, nachdem er mit RCA weltweiten Erfolg erzielt hatte, traf sich Elvis mit Johnny, Carl und Jerry Lee. Die vier hatten eine spontane Jam-Session, und Sam schaltete das Tonbandgerät ein. Das Material wurde 1981 als „Million Dollar Quartet“ veröffentlicht. Später wurden weitere Tracks entdeckt, was 1990 zur Veröffentlichung von „The Complete Million Dollar Session“ führte. Das Treffen wird manchmal als „Mount Rushmore des Rock 'n' Roll“ bezeichnet. Sam besuchte Elvis' Eröffnungskonzert im International Hotel im Jahr 1969.
Elvis betrat am 10. Januar 1956 zum ersten Mal das RCA Studio B in Nashville, zwei Tage nach seinem einundzwanzigsten Geburtstag. „Heartbreak Hotel“ wurde zur Aufnahme vorselektiert. Es war ein Lied von Mae Boren Axton und Tommy Durden. Es war ein Suizidlied, inspiriert von einem Zeitungsartikel, den Durden gelesen hatte und der über den Tod eines unbekannten Mannes berichtete, der von einem Hotelzimmerfenster sprang und eine Notiz hinterließ: „Ich gehe eine einsame Straße entlang.“
Elvis nahm das Lied mit seiner Band auf, zu der inzwischen Schlagzeuger D.J. Fontana neben Scotty und Bill gehörte. Auch RCA-Studiomusiker und Gitarrenlegende Chet Atkins gesellte sich dazu, ebenso wie der Pianist Floyd Cramer.
RCA hatte tatsächlich Schwierigkeiten, das Lied aufzunehmen. Sie wollten den Echo-Sound einfangen, für den Sun Records berühmt war, aber da das Studio viel größer war, erwies sich dies als schwierig, und sie wussten nicht, dass Sam Phillips zwei Tonbandgeräte mit einer leichten Zeitverzögerung verwendet hatte, um den Echo zu erzeugen. Das nächste Problem war Elvis' Tendenz, sich beim Singen zu bewegen. Die Lösung, wie von Elvis vorgeschlagen, war, sein Mikrofon in einem Flur zu positionieren. Der offizielle RCA-Produzent Steve Sholes glaubte, Elvis wisse, was er tat, und überließ es ihm, es auf seine Weise zu tun.
„Heartbreak Hotel“ wurde mit der Ballade „I Was the One“ gekoppelt und am 27. Januar 1956 als Single veröffentlicht. Die Single toppte sieben Wochen lang die Billboard 100 Singles-Charts, 17 Wochen lang die Country-Charts und erreichte Platz 3 der R&B-Charts. Keine frühere Aufnahme hatte jemals einen solch universellen Erfolg erzielt. Die Single machte Elvis auch einem weltweiten Publikum bekannt, auch in Großbritannien, wo sie Platz 2 erreichte. Der britische Sänger Cliff Richard würde später sagen, sie habe eine Generation zukünftiger Musiker inspiriert; niemand hatte zuvor etwas Vergleichbares gehört.
Es war Elvis' erste Single, die sich in den USA millionenfach verkaufte, ihm seine erste Goldene Schallplatte einbrachte und schließlich von der Recording Industry Association of America mit Doppelplatin ausgezeichnet wurde. Elvis spielte „Heartbreak Hotel“ zuletzt am 29. Mai 1977 im Baltimore Civic Centre.
