"Sex Is Not the Enemy" was written and recorded during sessions at the band's home base of Smart Studios in Madison, Wisconsin,^[8] and along with "Right Between the Eyes", was one of the first songs developed for the fourth record.^[9] Over the course of 2003, Garbage had been struggling to find an agreed-upon direction for the album.^[10] Vocalist and primary lyricist Shirley Manson had also been struggling with writer's block, while recovering from surgery to remove a cyst on her vocal cords.^[1] In August, Manson wrote in her online journal that "Sex Is Not the Enemy" sounded "like old school Garbage".^[11] However by the following month, the band's disintegrating dynamic ultimately escalated into a three-month long split and cessation of all recording activity.^[12]

After regrouping in Los Angeles to work with John King on some songs at the beginning of 2004, Garbage were prepared to return to Madison to overcome the difficulties that had derailed the previous years sessions.^[1] "We came up with a whole slew of songs in the first week [in Madison] ... Shirley wrote the lyrics to "Sex is Not the Enemy" ... suddenly words started pouring out of her. " drummer Butch Vig later recalled, "Because we almost lost the band, there was a certain sense of desperation when we got back in the studio. Duke and Steve really upped the ante with their guitar playing. Shirley's lyrics got much more topical socially and politically."^[13] Manson felt a need to respond to what she saw as the Bush administration clamping down on LGBT+ and reproductive rights and people's civil liberties.^[2] Guitarist Steve Marker considered it as nothing more than "a party song" until the subject matter was refocused.^[14] Around this time, Manson had seen the Super Bowl halftime show fall-out and incorporated how she felt about that into the song.^[15]

At least three different versions of "Sex Is Not the Enemy" evolved throughout the Bleed Like Me sessions; towards the end of recording, Manson re-sung the entire vocal, as the band decided to return to the original verse melody.^[16] Bass guitar parts were performed by Justin Meldal-Johnson, while drums were performed by Matt Walker, as Vig wanted to control the sound of some of the songs from "behind the glass" during the album sessions, which were engineered by Billy Bush.^[17] To record the "pumping energy" of the drums, room mics were placed to capture the natural sound of the drums, which was then compressed at tracking stage.^[17] The final recording was mixed by Vig at Smart Studios and mastered by Emily Lazar at The Lodge in New York City.^[18]

Of the song's lyrical matter, Manson described it as "sort of heavy, but it's coated in this really anthemic, upbeat party song."^[19] Manson was perplexed by the apparent hypocrisy of censorship on US television, when in her opinion there were much worse things shown on-screen that children were left to watch unsupervised,^[19] yet as the Iraq War raged on, the USA Today featured the SuperBowl incident on their cover for three days in a row instead. Manson felt the media "was only focusing on Janet's beautiful tit, which I thought was bizarre".^[15] "The chorus was just a tongue-in-cheek call to arms ... I get frustrated with certain restraints that are placed upon me because I'm a woman," Manson elaborated, "And, equally, men are shoved into a corner."^[20] At the completion of the album, Manson looked back and agreed, "'[It's] sort of a manifesto ... I had no idea it was, until I looked back and thought, 'this really is an anthem to my sexual politics'".^[14] Coming through in the verse was Manson's sympathy for committed same-sex couples fighting for their right to be married, while celebrities such as Nicky Hilton were able to abuse the institution ("and, besides the odd raised-eyebrow or two, totally get away with it just because they're heterosexual. lt's so unjust"). Manson used the song to register her protest that nobody she knew felt represented by the Bush administration.^[21]

On March 28, 2005, "Sex Is Not the Enemy" was first performed for a live audience at a five-song promo set for a Canal+ Album de la semaine broadcast. The following night, on the opening night of the Bleed Like Me tour,^[22] the song debuted onstage at Olympia in Paris. In 2016, "Sex Is Not the Enemy" was brought back into the set for the Strange Little Birds and 2017's Rage and Rapture tours.

Warner Music had originally scheduled "Bleed Like Me" as the worldwide second single from Bleed Like Me, however after the success of "Why Do You Love Me" in the UK charts, the label refocused onto "Sex Is Not the Enemy". Warner serviced a new radio mix of the song to broadcasters, however XFM was the only major radio station to playlist "Sex Is Not the Enemy"—neither Radio One or Radio 2 did. Ahead of the retail date, Garbage undertook some media interviews on TRL, Popworld, CD:UK and hit40uk,^[23] and headlined a sold-out concert at London's Brixton Academy^[2] and performed a slot at the Download Festival.^[24] Unlike the release of "Why Do You Love Me", where Garbage had performed the single on all the major TV shows, along with pre-records for the then-planned "Bleed Like Me" single, Garbage were unable to do the same for "Sex Is Not the Enemy".

On June 13, 2005, "Sex Is Not the Enemy" was released on CD, DVD and 7" vinyl formats.^[25] The single underperformed, debuting and peaking on the UK singles chart at number 24.^[26] On June 19, Garbage appeared at T4's televised Party on the Beach coast-side festival in Weston-Super-Mare, promoting "Sex Is Not the Enemy" and "Why Do You Love Me" in front of thousands of sun-baked revellers.^[27] Warners belatedly serviced a few club remixes of "Sex Is Not the Enemy" to DJs^[28] and on July 3 a digital bundle of the single and B-side "Honeybee" was made available on iTunes.^[29]

In September, "Sex Is Not the Enemy" was serviced to Australian radio and TV.^[30] The song was used to promote the band's final Bleed Like Me tourdates^[24] as well as the retail date for Bleed Like Me: Australian Tour Edition, a repackaged CD/DVD of the album for the Australian market. The bonus DVD featured the "Sex Is Not The Enemy" music video and "making of" documentary from the UK DVD single.^[31]

The music video for "Sex Is Not the Enemy" was directed by Sophie Muller and filmed on two consecutive nights of April 20 and April 21.^[32] On the first day of shooting, both Manson and Muller shot montage scenes in a New York City hotel room and at a street corner down from Times Square.^[33] "She was getting up on a soapbox with a bullhorn and just yelling at people," Butch Vig later recalled, "And it was funny, 'cause people thought, 'Oh, another crazy woman'... They just ignored her."^[32]

On the second day the band filmed live footage onstage at their show at Washington D.C.'s 9:30 Club.^[34] This section of the video referenced both Janet Jackson's "wardrobe malfunction" and Jim Morrison's 1969 arrest for alleged on-stage indecent exposure,^[1] choreographing a sequence where Manson exposed her breasts to the audience (in reality, a flesh-coloured bra) and dragged off-stage by hired actors posing as D.C. cops.^[33] The rest of Garbage dropped instruments mid-song and stormed off. The audience were not told of the stunt and afterwards heckled the venue security.^[33] Some of the audience assumed they had fallen victim to a Punk'd stunt.^[32]

On May 15, the "Sex Is Not the Enemy" video streamed exclusively from Garbage.com,^[35] a day before it was serviced to music stations.^[36] The video premiered in the United States on July 4^[37] and in Australia on September 11.^[30] The "Sex Is Not the Enemy" video became available to download on digital stores in 2006 and a slightly different edit of the clip uploaded to VEVO in 2015.^[38]

The "Sex Is Not the Enemy" single release was backed with b-sides "Honeybee" and "Never Be Free", both recorded during the album sessions for Bleed Like Me. Butch Vig described "Honeybee" as "Neil Young-esque, with a druggy feel",^[39] while Manson described it as "pretty dark and twisted. It's a lusty, yearning moan".^[40] "Honeybee" featured drums performed by Matt Walker, while "Never Be Free" credited John5 with guitar. All three tracks were written and produced by Garbage, although "Never Be Free" may have originally been a John Lowery co-write.^[41] Producer James Michael may have also worked on the track at one point.^[42] An acetate of an early version of "Never Be Free" leaked from Chrysalis Music Group in 2003, but the track did not end up on the internet.^[41] Both b-sides were ported over to the European and Australian "Run Baby Run" singles.^[4]

In June 2005, Warner serviced three remixes to dance radio stations, one remix by filthy-electro duo Devil's Gun and a vocal mix and dub mix produced by breakbeat Ils. By the end of August, two separate 12" vinyl white labels were in circulation featuring further remixes of the song produced by Freaks^[43] and by DJ Hell/Fischerspooner side-project Naughty.^[44]

"Sex Is Not the Enemy" was generally well-received by music critics, a number of whom highlighted the track in their Bleed Like Me album reviews. Sian Llewellyn, in her Classic Rock review, thought the track was a "fuzzed up work of pop rock genius—complete with one of those cut-all-the-instruments-except-the-drums-and-the-vocal clap along moments" adding that "you can already hear its 'a revolution is the solution' chant reverbating through concert halls across the land".^[45] while Chuck Arnold of People described the song as "anthemic".^[46] Reviewers for NME were rather critical, Dan Martin writing that "tracks on the sober second-half [of the album] like "Sex Is Not the Enemy" revert to factory settings" and "could have been on any Garbage record of the past ten years,"^[15] while in their single review, their journalist wrote "a sludgy-yet-shiny rock song that rages against state prudishness while sounding like a less-gay re-write of "Cherry Lips (Go Baby Go!)". Good drums though."^[47] Mike Shallcross, of Time Out London, declared Manson's lyrics as banal, adding "trying to gauge whether this song contradicts Pat Benatar's "Stop Selling Sex As A Weapon" and pondering whether the U.N. should start sending inspection teams to Sex".^[48] Contrastingly, Leander Williams, of Time Out New York, wrote "Garbage's adventures in Wall of Sound multi-tracking make what's been called a return to basics impossible. What's interesting is how the band tops the guitar and explosive glitches of present day rock with the Blondie-tronic keyboard riffs of new wave pop on "Sex Is Not the Enemy" ... amongst others".^[49] Some reviewers also noted the song's perceived similarity to the bassline of The Breeders 1993 single "Cannonball".

• "Sex Is Not the Enemy" music video