Lipstick Traces (On a Cigarette) è un brano scritto da Allen Toussaint sotto lo pseudonimo di Naomi Neville. È stato registrato per la prima volta dal cantante Benny Spellman a New Orleans nel 1962 e pubblicato come singolo il 2 febbraio dello stesso anno. Il singolo arrivò alla ventottesima posizione nella classifica R&B di Billboard e all'ottantesima della Billboard Hot 100[1]. Il lato B era Fortune Teller, reso famoso dalla cover dei Rolling Stones. Nel singolo originale, i cori erano eseguiti da Irma Thomas e Willie Harper, anch'esse scritturate dalla Mirit Records[2].
Gli O'Jays ne hanno registrato una cover nel 1965, che è stata pubblicata come singolo con il numero di serie 66102; il singolo giunse alla ventottesima posizione della classifica R&B e alla quarantottesima di quella pop[3]. È stata inclusa, nello stesso anno, nell'album Comin' Through[4];
Ringo Starr ha incluso una cover nel suo album Bad Boy del 1978. Negli USA è stata pubblicata come singolo, con al lato BOld Time Revolvin', il 17 aprile 1978[5];
