Chcąc poprawić sobie humor w przerwie podczas sesji, zaczął grać na gitarze utwór Arthura Crudupa „That’s All Right, Mama”, co Phillips niezwłocznie zaczął nagrywać. Trzy dni później DJ Dewey Phillips puścił nagranie w swojej audycji Red, Hot and Blue w radiu WHBQ. Słuchacze dzwonili do studia, żeby dowiedzieć się, kto jest wykonawcą piosenki, a wielu odbiorców uważało go za czarnoskórego.
19 lipca 1954 wydał debiutancki singiel „That’s Alright (Mama)/Blue Moon of Kentucky”, z którym pod koniec miesiąca dotarł do trzeciego miejsca na liście Memphis Country Music Chart. 10 sierpnia w Overton Park Shell Auditorium zagrał swój pierwszy koncert, na którym został przychylnie przyjęty przez publiczność. We wrześniu odbył kolejną sesję nagraniową, podczas której zarejestrował piosenki – „Good Rockin’ Tonight”, „I Don’t Care If the Sun Don’t Shine”, „Uncle Pen” i „Just Because”. W tym samym miesiącu wystąpił w Grand Ole Opry w Nashville, gdzie został wygwizdany przez konserwatywną widownię, która była zszokowana ekspresją i ruchami scenicznymi Presleya.