"Lipstick Traces (on a Cigarette)" is a song first recorded by New Orleans singer Benny Spellman in 1962. It was written by Allen Toussaint under the pseudonym Naomi Neville. The song became Spellman's only hit record, peaking at number 28 on the Billboard R&B chart and number 80 on the Billboard Hot 100 pop chart. The flip side of the single was "Fortune Teller", made famous by The Rolling Stones cover among others.
"Lipstick Traces (on a Cigarette)" was recorded in New Orleans on February 2, 1962. The background vocals were done by label mates Irma Thomas and Willie Harper.
The song has been covered by number of artists and bands. One of the earliest covers was done by The O'Jays in 1965. (Imperial single 66102) Their version peaked on the R&B chart at #28 and #48 on the pop chart. It was included in the album Comin' Through (Imperial 9290), released in the same year.