Naslov pjesme se odnosi na cipele od jelenje kože, koje su 1950-ih kao dio svoje uniforme nosili pripadnici američkog ratnog zrakoplovstva. Perkinsu je 1955. prilikom zajedničke turneje Johnny Cash predložio da napiše pjesmu o takvim cipelama; Perkins je ispočetka mislio da je to loša ideja. Inspiraciju mu je, međutim, dao događaj na jednom plesu, kada je muškarac svojoj partnerici, koja nije znala pratiti njegov korak, rekao da "ne gazi njegove cipele od jelenje kože".