Elviksen ensimmäisen RCA-singlejulkaisun "Heartbreak Hotel" noustua maaliskuun alussa 1956 singletilaston kärkeen, yhtiön levypomot olivat vakuuttuneita artistinsa potentiaalista levymyyjänä, ja julkaisivat kiireellä 13. maaliskuuta Presleyn ensialbumin, nimeltään "Elvis Presley". Pikaisella aikataululla koottu albumi sisälsi puoliksi vanhaa Elviksen Sun-yhtiölle levyttämää materiaalia, ja puoliksi alkuvuoden RCA-sessioiden julkaisemattomia raitoja. Jo maaliskuun lopussa levy oli ylittänyt 300 000 kappaleen myyntimäärän, ollen näin RCAn ensimmäinen miljoonan dollarin albumi (levyn vähittäismyyntihinta $3.98). Kiireellisen julkaisuaikataulun vuoksi Elvistä ei saatu studiokuvaan, ja kannessa käytettiin edellisenä vuonna Floridan-keikalla otettua mustavalkoista valokuvaa, joka poikkeaa tyylillisesti myöhempien albumikansien linjasta.
The Clash -yhtyeen albumin London Calling kanteen on kopioitu Elvis Presley -albumin kannen typografia.
