Sparks' last album was released in 1988, and while it scored a couple of club hits in the US, had not been commercially successful. Critically the group had been receiving mixed reviews since their 1984 album Pulling Rabbits Out of a Hat. While promoting Interior Design, Sparks 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 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-musician Christi Haydon voicing the lead character. Russel Mael had initially met Haydon when he admired her look while she was working on the cosmetics counter of a department store . 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 sound that returned towards 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.