The song received a positive reception from music critics and became the band's most successful single worldwide reaching No. 3 in Norway, the top five in Australia, and the top twenty in the United Kingdom, Ireland, Germany and New Zealand. It also received a limited promotional release in the United States. The song was certified Gold in Germany in 1996 for 250,000 copies sold, despite never reaching the top ten in that country. It charted again at the bottom of the German Top 100 in 2008 because of digital downloads after it was used in a soap opera. "Where the Wild Roses Grow" was also certified Gold in Australia for selling 50,000 copies.
Cave was inspired to write "Where the Wild Roses Grow" after listening to the traditional song, "Down in the Willow Garden", a tale of a man courting a woman and killing her while they are out together. Cave arranged this tale as second of two B-sides, "The Ballad of Robert Moore & Betty Coltrane" / "The Willow Garden", released on the CD-Maxi single version.
Where The Wild Roses Grow was written very much with Kylie in mind. I'd wanted to write a song for Kylie for many years. I had a quiet obsession with her for about six years. I wrote several songs for her, none of which I felt was appropriate to give her. It was only when I wrote this song, which is a dialogue between a killer and his victim, that I thought finally I'd written the right song for Kylie to sing. I sent the song to her and she replied the next day.
—Nick Cave, quoted in Molly Meldrum presents 50 years of rock in Australia (2007)
"one of pop music's most violent and distressing lyrics" and "when Kylie Minogue sings these words, there is an innocence to her that makes the horror of this chilling lyric all the more compelling".
Nick Cave and the Bad Seeds and Kylie Minogue first performed the song publicly on 4 August 1995 in Cork, Republic of Ireland.
The video for this song, commissioned by Emma Davies for Mute Records, shot by director Rocky Schenck and produced by Nick Verden for Atlas Films, shows Kylie Minogue in character, apparently having been murdered by Nick Cave's character. We see her in ghost-like form and also in a river in a pose reminiscent of Millais' painting Ophelia. The video ends with Cave's character putting a rose in Minogue's mouth and closing her eye lids.