The song was written by Sting of the Police. The lyric "I'm a three-line whip", often assumed to be a reference to sadomasochism, is in fact an allusion to the voting instructions issued to British members of parliament to cast their votes according to the party line. Sting explained this in an interview: "Whatever party's in power in Parliament, if it's a really important vote, you get a one-line whip. If it's incredibly important, you have a two-line whip, and something monumentally important is a three-line whip."
"Demolition Man" was released as the lead single from Grace Jones's 1981 album Nightclubbing. The song was performed on A One Man Show tour, featuring marching "Joneses" (stand-ins wearing Grace Jones masks), and included in the documentary film. A still picture from the video was later used for the cover of 1982 singles "Nipple to the Bottle" and "The Apple Stretching".
The song would later be performed by Sting during his solo career and released in 1993 on an EP of the same name in support of the Demolition Man film. This version of the song plays during the film's end credits.
In the 53rd episode of Beavis and Butt-head, "True Crime", aired in 1993, the pair were watching Jones' "Demolition Man" video from A One Man Show.
A live version of the song performed by Sting was featured in the game Guitar Hero World Tour along with an in-game representation of Sting himself, which becomes an unlockable character upon completing the song in the bass career.
An excerpt of Jones' performance of the song from A One Man Show was displayed as a part of the Postmodernism: Style and Subversion 1970-1990 temporary exhibition at London's Victoria and Albert Museum in 2011 and 2012.