Rob Grant and Doug Naylor wrote the lyrics for the comedic love song, in which the words of the chorus are delivered in an increasingly-unintelligible manner by the lovestruck singer.

In the documentary feature Settling the Score included in the Red Dwarf VI DVD (2005), Goodall claimed the Diana Ross song "Chain Reaction" was an influence on his music for "Tongue Tied."

"Tongue Tied" was staged and filmed on 9 July 1988 as an upbeat-pop song-and-dance number for "Parallel Universe", broadcast on 11 October 1988 as the final episode of the second season of Red Dwarf.

The song was recorded in Portobello Road, Notting Hill and accompanied by a music video featuring John-Jules in character as the Cat and Duane Dibbley, backed by fellow Red Dwarf cast members Chris Barrie, Craig Charles, Robert Llewellyn, Norman Lovett, and Hattie Hayridge, as well as Charles Augins and Elvis impersonator Clayton Mark (who guest-starred in the 1991 Red Dwarf episode "Meltdown").

The "Tongue Tied" single was released on 11 October 1993 (ten years to the day after the original version of the song premiered in Son of Cliché), coinciding roughly with the launch of the sixth season of Red Dwarf on television.

The first 20 minutes comprises a longform version of the "Tongue Tied" music video, with a framing device starring Danny John-Jules as Leo Davis, a cleaner in a film studio.