Su primer disco de oro fue «Heartbreak Hotel», grabado en enero de 1956.