Sparks' last album was released in 1988, and while it had scored a couple of club hits in the US, had not been commercially successful. Critically the group had received mixed reviews since their 1984 album Pulling Rabbits Out of a Hat. While promoting Interior Design, Sparks had banded together with the French duo Les Rita Mitsouko and released the single "Singing in the Shower" which was a moderate hit in France. Sparks then went on a temporary hiatus while the brothers had spent the late 1980s and early 1990s concentrating on film-making, particularly an attempt to make a Japanese comic strip, Mai, The Psychic Girl, into a movie. They had hoped to have Tsui Hark direct with the actress Christi Haydon voicing the lead character. Haydon's only experience at the time had been as a long running extra of the TV show Star Trek: The Next Generation. Despite interest from Tim Burton and six years' work on the project, it came to nothing.
In 1993 Sparks returned to the studio and released the stand-alone single "National Crime Awareness Week", and wrote and produced the single "Katharine Hepburn" for Christi Haydon. Gratuitous Sax & Senseless Violins followed in November the next year. It was produced by the duo without an additional backing band. The album had a modern sound that returned to the European-synthesiser orientated sound of No. 1 In Heaven. However the songs retained an emphasis on pop song structure and a sound that was only slightly removed from that of Pet Shop Boys. The album was toured with Christi Haydon complementing the brothers on drums, as well as appearing in videos for the group. The a cappella title track "Gratuitous Sax" looked back to the equally brief opener of the band's 1974 album; Propaganda. "When Do I Get To Sing "My Way"" makes reference to the Frank Sinatra signature-tune "My Way".
Gratuitous Sax & Senseless Violins became Sparks most successful album in Germany reaching #29 and scored three hits on the German Singles chart. While the album only reached #150 on the UK Albums Chart, the singles did well enough to return the group to the top forty, the first time since "Beat the Clock" in 1979. The lead single "When Do I Get To Sing "My Way""; made #7 in Germany, #38 in the UK (it was re-released in May 1995 and peaked at #32). The second single "(When I Kiss You) I Hear Charlie Parker Playing"; retitled "When I Kiss You (I Hear Charlie Parker Playing)" #61 in Germany and #36 in the UK. The final single "Now That I Own The BBC" did less well making #81 in Germany and #60 in the UK.
"When Do I Get To Sing "My Way"" and "When I Kiss You (I Hear Charlie Parker Playing)" managed to chart across Europe, and recommenced Sparks' popularity on the US BillboardHot Dance Music/Club Play chart where they reached No. 9 and #24.
Japanese editions of the album included "When I Kiss You (I Hear Charlie Parker Playing) (Bernard Butler's Mix)" as a bonus track. The album was re-released as first in the series Sparks – The Collection in 2006 on the groups' own record label Lil' Beethoven Records. This re-release featured new artwork, additional sleeve-notes and was packaged in a digipak-sleeve.