En 18 mois, Sun Records a sorti cinq singles d'Elvis. Le plus réussi d'entre eux était la combinaison de « I Forgot to Remember to Forget » et « Mystery Train », le dernier single, enregistré en 1955 et qui a atteint le sommet du US Country Chart en février 1956. C'était le premier single numéro un d'Elvis dans un classement national.
À cette époque, Elvis avait déjà été signé par le Colonel Tom Parker, un promoteur de spectacles de country, avec Hank Snow. Le Colonel Parker avait présenté Elvis à ses spectacles, et après avoir vu Elvis surpasser tous les artistes country établis de l'époque lorsqu'il est monté sur scène, Parker a décidé de signer Elvis avec un contrat de gestion exclusif. Elvis a signé le contrat avec le Colonel Parker le 15 août 1955, avec l'approbation de ses parents, car il n'avait pas encore vingt et un ans. Vernon a été facilement persuadé, mais Gladys a mis du temps à accepter, car elle ne faisait pas entièrement confiance au Colonel.
Le Colonel Parker avait jeté son dévolu sur RCA Victor et a contribué à négocier un accord avec eux pour payer un montant record de 35 000 $ à Sun Records. Bien qu'Elvis hésitait à quitter Sam, Sun Records n'avait pas la capacité de répondre à la demande de disques d'Elvis ni de les distribuer à l'international. Sam expliquerait plus tard qu'il avait lutté financièrement si longtemps que, lorsque l'occasion s'est présentée, il a fixé un prix qu'il ne pensait pas qu'on accepterait, ce qui lui permettrait de garder Elvis. Cependant, lorsque RCA a accepté, Sam n'était pas en position de refuser. L'accord a également entraîné un bonus de 5 000 $ pour Elvis. Aujourd'hui, l'accord représenterait environ 500 000 $. Le contrat entre RCA, Sun et Elvis a été signé le 20 novembre 1955, Sam conseillant à Elvis : « Ne les laissez pas vous dire quoi faire, ne perdez pas votre individualité. » Sam Phillips a ensuite contribué à lancer les carrières de Johnny Cash, Carl Perkins, Jerry Lee Lewis et Roy Orbison. Sam et Elvis sont restés amis. Lors d'une visite au studio le 4 décembre 1956, après avoir connu un succès mondial avec RCA, Elvis a retrouvé Johnny, Carl et Jerry Lee. Les quatre ont fait une jam session impromptue, et Sam a allumé la machine à bandes. Le matériel est sorti en 1981 sous le nom de « Million Dollar Quartet ». D'autres morceaux ont été découverts plus tard, entraînant la sortie de « The Complete Million Dollar Session » en 1990. La rencontre est parfois appelée le « Mount Rushmore du Rock 'n' Roll ». Sam a assisté au concert d'ouverture d'Elvis à l'International Hotel en 1969.
Elvis est entré pour la première fois au RCA Studio B de Nashville le 10 janvier 1956, deux jours après son vingt et unième anniversaire. « Heartbreak Hotel » avait été présélectionné pour l'enregistrement. C'était une chanson écrite par Mae Boren Axton et Tommy Durden. C'était une chanson sur le suicide inspirée par un article de journal que Durden avait lu, rapportant la mort d'un homme non identifié qui avait sauté par la fenêtre d'un hôtel, laissant une note disant : « Je marche dans une rue solitaire. »
Elvis a enregistré la chanson avec son groupe, qui comprenait désormais le batteur D.J. Fontana aux côtés de Scotty et Bill. Le musicien de session RCA et légende de la guitare Chet Atkins s'est également joint, ainsi que le pianiste Floyd Cramer.
RCA a eu du mal à enregistrer la chanson. Ils voulaient capturer le son d'écho qui faisait la renommée de Sun Records, mais le studio étant beaucoup plus grand, cela s'est avéré difficile, et ils ignoraient que Sam Phillips avait utilisé deux magnétophones avec un léger décalage temporel pour obtenir l'écho. Le problème suivant était la tendance d'Elvis à bouger en chantant. La solution, suggérée par Elvis, fut de positionner son microphone dans un couloir. Le producteur officiel de RCA, Steve Sholes, pensait qu'Elvis savait ce qu'il faisait et le laissa faire à sa manière.
« Heartbreak Hotel » a été associé à la ballade « I Was the One » et publié en single le 27 janvier 1956. Le single a dominé le classement des singles Billboard 100 pendant sept semaines, le classement Country pendant 17 semaines, et a atteint la 3e place du classement R&B. Aucun enregistrement précédent n'avait jamais connu un tel succès universel. Le single a également fait découvrir Elvis à un public mondial, y compris au Royaume-Uni, où il a atteint la 2e place. Le chanteur britannique Cliff Richard dirait plus tard qu'il a inspiré une génération de futurs musiciens ; personne n'avait jamais rien entendu de tel auparavant.
Ce fut le premier single d'Elvis à se vendre à un million d'exemplaires aux États-Unis, lui rapportant son premier disque d'or et finalement certifié double platine par la Recording Industry Association of America. Elvis a interprété « Heartbreak Hotel » pour la dernière fois au Baltimore Civic Centre le 29 mai 1977.
