"Don't Be Cruel" is geschreven door Otis Blackwell en geproduceerd door Steve Sholes. Het is het eerste nummer dat Hill & Range, de uitgeverij van Presley, aan hem gaf zodat hij het op kon nemen. Blackwell vond het niet erg dat hij 50% van de royalty's af moest staan en dat Presley werd genoemd als co-auteur, zodat de "beste nieuwe zanger het op kon nemen", maar hij had het nummer al verkocht voor 25 dollar. Volgens uitgever Freddy Bienstock kreeg Presley co-auteurschap voor enkele nummers, omdat "Elvis in het begin van zijn carrière niet altijd blij was met een bepaalde tekstregel en maakte hij een aantal wijzigingen, dus het is niet wat je een 'cut-in' zou noemen. Zijn naam verscheen niet na het eerste jaar. Maar als Presley het nummer goed vond, mochten de schrijvers kiezen of zij een miljoen dollar zouden krijgen, met als voorwaarde dat Elvis een derde van de royalty's zou ontvangen."
Presley nam "Don't Be Cruel" op 2 juli 1956 op, tijdens dezelfde sessie waarin hij ook "Hound Dog" en "Any Way You Want Me" opnam. De instrumenten werden gespeeld door de gebruikelijke achtergrondband van Presley: gitarist Scotty Moore (waarbij Presley hem ondersteunde), basgitarist Bill Black, drummer D.J. Fontana en achtergrondzangers The Jordanaires. Alhoewel enkel Steve Sholes werd genoemd als producer, is in een aantal takes te horen dat Presley optrad als co-producer: hij koos het nummer uit, herschreef het piano-arrangement, en nam 28 takes op voordat hij tevreden was.
Op 13 juli 1956 werd "Don't Be Cruel" als dubbele A-kant met "Hound Dog" uitgebracht als single. De nummers stonden echter gesplitst in de hitlijsten: waar "Hound Dog" tot de tweede plaats in de Amerikaanse Billboard Hot 100 kwam, behaalde "Don't Be Cruel" de eerste plaats, waar het elf weken bleef staan. Het werd de op één na grootste hit van 1956, achter "Heartbreak Hotel", eveneens een nummer van Presley. In het Verenigd Koninkrijk bleef het een B-kant, maar in 1978 kwam het na het overlijden van Presley tot plaats 24 in de UK Singles Chart. In Vlaanderen behaalde de single plaats 23 in de voorloper van de Ultratop 50. In 2002 werd het nummer opgenomen in de Grammy Hall of Fame, en in 2004 zette het tijdschrift Rolling Stone het op plaats 197 in hun lijst The 500 Greatest Songs of All Time.
"Don't Be Cruel" werd een aantal keren gecoverd. The Beatles zouden het live hebben gespeeld tussen 1959 en 1961, alhoewel er geen opnames van bestaan. Tijdens de Get Back-sessies van 1969 heeft de band een versie opgenomen, maar deze versie is nooit uitgebracht. De voormalige Beatles John Lennon, Ringo Starr en Pete Best, alsmede de oudere bandgenoten van Lennon (als The Quarrymen) en Tony Sheridan, die in de beginperiode van de band met hen heeft samengewerkt, hebben wel opnames uitgebracht.
Andere artiesten die "Don't Be Cruel" hebben opgenomen, zijn onder meer Bill Black, Cheap Trick, Devo, Neil Diamond, Connie Francis, Merle Haggard, Debbie Harry, Jack Jersey, The Judds, Jerry Lee Lewis, Annette Peacock, The Smithereens, Marty Stuart, Billy Swan en Jackie Wilson. Presley zou zo onder de indruk zijn van de versie van Wilson, dat hij bij latere live-optredens het nummer speelde zoals hij dit deed. In de Verenigde Staten werden de versies van Bill Black (1960), The Judds (1987) en Cheap Trick (1988) hits, terwijl in enkele Europese landen de opname door Billy Swan (1975) een hit werd. In Nederland stond het in twee versies in de hitlijsten. In 1975 behaalde Mike Berry de veertiende plaats in zowel de Top 40 als de Nationale Hitparade, terwijl in 2003 René Shuman en Angel-Eye onder de noemer Shuman & Angel-Eye de dertiende plaats in de Top 40 en de twaalfde plaats in de Mega Top 100 haalden.
