De song werd opgenomen in januari 1956 in Nashville. Hij werd Elvis eerste single voor RCA. Hij werd uitgebracht met als B-kant “I Was het One” op 27 januari 1956.
Aangemoedigd door zijn partner, Colonel Tom Parker, had Country Ster Hank Snow Presley onder zijn hoede genomen voor de Hank Snow Jamboree Attracties. Presley was erg onder de indruk van een 40-jarige publiciste (reclamemaker), Mae Boren Axton, wanneer hij met de Snow tour naar Florida kwam in mei 1955.
Zij besloot samen met een lokale muzikant, Tommy Durden, een song voor Elvis te schrijven.
Tommy Durden was een steelgitarist in Smiling Jack Haring en zijn Swing Billies, en Mae Boren Axton, een lerares in Jacksonville, Florida. Zij schreven “Heartbreak Hotel” in minder dan een half uur in 1955. Zij was de moeder van Hoyt Axton’s, en ook een publicist voor Hank Snow..
Durden toonde haar een verhaal uit de Miami Herald over een hotelgast die zelfmoord pleegde en een briefje naliet met als tekst “I walk a lonely street”
Ja, dit kon een goeie bluesline worden : “a lonely man, a lonely street and a man’s life is over”.
Na een half uurtje was de song er. Aan Glen Reeves werd gevraagd om er een demo van te maken. Men bood hem een songwriting credit aan maar hij deed het gratis. In november 1955 speelde Axton de demo voor Presley en hij reageerde meteen: “Hot dog, Mrs Axton, play that again!”
Interessant is dat Elvis Presley de demo van Reeves noot voor noot imiteerde.
“Heartbreak Hotel” was de tweede song die Elvis opnam voor RCA Victor op 10 januari 1956 tijdens zijn debuut sessie in 1.525 McGavock Street in Nashville. Hij kwam naar de studio met een kant en klaar nummer, direct gereed om op te nemen, zonder op zoek te gaan naar enige goedkeuring van RCA en, hoewel producer Steve Sholes een beetje ongerust was, nam hij het nummer op denkende dat Presley wel wist wat hij deed.
De meeste anderen bij RCA Victor dachten dat dit een vergissing was, vooral omdat het nummer totaal anders was dan wat Elvis bij SUN had opgenomen.
Elvis nam het op met zijn vaste band met Scotty Moore, Bill Black en DJ Fontana, aangevuld met gevestigde RCA muzikanten Chet Atkins op gitaar, en Floyd Cramer op piano.
De geluidskwaliteit van deze eerste sessie was niet goed, en ‘Heartbreak Hotel’ was het ergste van allemaal. Chet Atkins speelde rhythm gitaar en Floyd Cramer werd toegevoegd op piano, samen met een volledig overbodig vocaal trio onder leiding van Gordon Stoker, zanger van The Jordanaires. Scotty Moore’s gitaar klinkt bijzonder, irritant blikkerig, Cramer is te prominent en de hele track klinkt alsof hij werd gemaakt onder water in een broodtrommel. Het was een schandelijke opname voor 1956, maar een HIT met hoofdletters voor Presley
Ondanks al deze tekortkomingen, bereikte ‘Heartbreak Hotel’ de Billboard charts in maart. Het was nummer een voor acht weken in de pop charts en nummer drie in de R&B charts.
