Главным заинтересованным лицом был весельчак Стив Шоулс, художественный руководитель Ар-си-эй, ответственный за подбор артистов ритм-энд-блюза и кантри-энд-вестерн
Шоулс одним из первых разглядел, какие перспективы открываются перед индустрией грамзаписи в Нэшвилле, нарождающейся столице кантри, после взлета популярности «Grand Ole Opry». Руководство Ар-си-эй не сочло целесообразным открывать офис так далеко от Нью-Йорка, и Шоулсу поначалу пришлось записывать артистов в пресвитерианской церкви Нэшвилла. Договоренности пришел конец, когда пастор обнаружил под одной из скамей спрятанную бутылку водки и прогнал Шоулса, объявив его агентом коммунистов. Шоулс тогда открыл студию звукозаписи в полуразрушенном здании методистского канала телерадиовещания, официально положив начало процветающей индустрии, которая потом принесла целое состояние столице Теннесси.
Ответственность за заключение контракта с Элвисом полностью легла на плечи Шоулса, начальство Ар-си-эй не скрывало, что на карте — его будущее. «Меня вызвали в дирекцию, которая хотела получить гарантии того, что все расходы окупятся уже в первый год. Я сглотнул слюну и сказал, что, по-моему, это возможно, но откуда мне знать?» — вспоминал Шоулс в 1967 году, за год до своей смерти. Единственная надежда на быструю окупаемость капиталовложений компании была в том, чтобы выйти за рамки стиля кантри, привлечь более широкие круги любителей поп-музыки, о чем и говорилось в статье, помещенной в «Биллборд» сразу после заключения исторического контракта: «Хотя „Сан“ раскручивала Пресли в основном среди любителей кантри-энд-вестерна, Ар-си-эй рассчитывает взять все призы, бросив своего нового артиста сразу на все фронты: поп, ритм-энд-блюз и кантри-энд-вестерн. Великий маниту „сорокапяток“ Стив Шоулс тем не менее намеревается записывать Пресли под такой же аккомпанемент, как у „Сан“: электрогитара, контрабас и ударные, дав в руки самому Пресли бас-гитару».
Не дожидаясь сеансов, назначенных на январь 1956 года, Ар-си-эй решила прозондировать почву в начале декабря, выпустив под своей маркой последний сингл Элвиса, вышедший в фирме «Сан», —
Этот успех в полутонах, которого было недостаточно, чтобы стимулировать продажи на национальном уровне, все-таки позволил приободриться, и Стив Шоулс вызвал Элвиса 10–11 января 1956 года в Нэшвилл на один из сеансов, которые имели решающее значение для карьеры их обоих. За эти два дня были записаны пять песен, в том числе «I Got a Woman» («У меня есть женщина») Рея Чарлза и «Money Honey» — хит трехлетней давности, открывший негритянскую группу Дрифтерсов, а также новая композиция под названием «Heartbreak Hotel» («Отель, где разбиваются сердца»).
Эту песню Элвису предложила за несколько недель до того Мэй Борен Акстон — учительница, с которой он познакомился во Флориде через полковника Паркера. Акстон подрабатывала сочинением статей для разных журналов и в результате стала составлять пресс-досье по просьбе полковника, когда его артисты выступали в окрестностях Джексонвиля. Побывав на зажигательных концертах Элвиса во Флориде весной и летом 1955 года, она вместе с другом написала для него балладу, сильно отличавшуюся своей мрачной окраской от сентиментальных шлягеров той поры.