The song juxtaposes "Libertango", an Argentine tango classic written by composer and bandoneonist Astor Piazzolla (first recorded by Piazzolla himself in 1974), against a tango, reggae and chanson sound[1] and new lyrics penned by Jones herself and Barry Reynolds.

The song includes spoken parts in French, written by actress Nathalie Delon: "Tu cherches quoi?

Recorded in Nassau, Bahamas, with Sly and Robbie, Wally Badarou, Barry Reynolds, Mikey Chung, and Uziah "Sticky" Thompson, aka the Compass Point Allstars under Chris Blackwell's and Alex Sadkin's direction, "I've Seen That Face Before" was released as the second single from Jones' album Nightclubbing, after "Demolition Man" made no chart impact.

It met with a commercial success, reaching Top 20 in no fewer than five European countries, including number 1 in Belgium, and now counts as one of Jones' signature tunes.

[3] It begins with a picture of Grace wearing a tall black hat and her face concealed under a three-piece paper mask.