Presley made appearances in four consecutive weeks on the Dorsey Brothers television program Stage Show in early 1956, on January 28, February 4, February 11, and February 18. RCA wanted an album in the stores fast to capitalize both on the nationwide TV exposure and the success of his first hit single on the pop charts with "Heartbreak Hotel", swiftly climbing to the top after its release on January 27. At the same time, there had only been two series of Presley recording sessions for RCA Victor by the end of the Dorsey stint, after which Presley and his band were back on the road. Those two sessions yielded an additional eleven tracks, almost enough to fill an entire LP, although some tracks had singles potential. In the 1950s, general practice dictated tracks having greater commercial potential to be released as singles, with tracks of lesser appeal placed on albums; as such, RCA Victor neither took all eleven tracks and simply made an album, nor placed the already released and briskly-selling "Heartbreak Hotel" on it. The rights to the Sun Studio tapes had transferred to RCA Victor with the sale of his contract, so five previously unreleased Sun songs, "I Love You Because", "Just Because", "Tryin' to Get to You", "I'll Never Let You Go (Little Darlin')", and "Blue Moon" were added to seven of the RCA Victor sessions tracks to bring the running time of the album up to an acceptable length. Phillips produced the sessions at Sun, and no producer was officially listed for the RCA Victor sessions, leading to the belief that Presley himself produced them.
As the Sun tracks were mostly country-styled, Elvis and RCA Victor leavened the selections with covers of recent rhythm and blues songs. Two of these, "Money Honey" by Jesse Stone, known to Elvis from a version by Clyde McPhatter, and Ray Charles' 1955 hit "I Got a Woman", had been in Presley's live act for a year. A third was the frenetic announcement to the world of the existence of Little Richard in 1955, "Tutti Frutti". A rockabilly number that was believed to be a potential hit and could hold its own with the R&B material, "Blue Suede Shoes", was not initially released as a single from a promise by Sholes to Sam Phillips to protect the career of another Sun artist, Carl Perkins, the author of the song. Instead, it was diverted into being the opening track on the album.
On August 31, 1956, RCA Victor took the unusual step of releasing the entire album as singles, which undoubtedly kept the new single released simultaneously, "Shake, Rattle and Roll" backed with "Lawdy Miss Clawdy," from reaching the charts. However, "Blue Suede Shoes", released in single form as a part of this experiment by RCA Victor, kept the promise to Phillips and Perkins by waiting over eight months since the song's release on Sun and made it to number 20 on the singles chart.
The cover is ranked number 40 on Rolling Stone's list of the 100 greatest album covers, published in 1991. The iconic photograph of Elvis was taken at the Fort Homer Hesterly Armory in Tampa, Florida, on July 31, 1955. Initially, it was thought that Popsie Randolph took the image featured on the front cover, since the album only credited one photographer. However, in August 2002, Joseph A. Tunzi documented that the actual photographer was William V. "Red" Robertson of Robertson & Fresch. The Popsie credit attributed to the album only applied to a series of photos featured on the back cover, taken in New York City in early December 1955, shortly after Presley had signed with RCA Victor. Tunzi was quoted in the Tampa Tribune as saying, "Forget about Popsie. Popsie did not take that photo." 
The graphic and photo were also used on an EP and a double-EP comprising songs from this album, also released in March 1956.
RCA first reissued the original 12 track album on compact disc in 1984. This issue, in reprocessed (fake) stereo sound, was quickly withdrawn and the disc was reissued in original monophonic. In 1999, RCA reissued the album with an altered running order, adding on six bonus tracks from three non-album singles, including the chart-toppers "Heartbreak Hotel" and "I Want You, I Need You, I Love You." In 2005, the album was reissued again, remastered using DSD technology with the six bonus tracks appended in standard fashion. A two-disc set was released on the Follow That Dream collectors label on August 15, 2006, with bonus tracks and numerous alternate takes.