“Where The Wild Roses Grow” foi, em vários sentidos, o joker da carreira de Nick Cave e dos seus Bad Seeds. Foi o single de avanço para o extraordinário Murder Ballads, disco conceptual de 1996 versando sobre assassinatos, desde reais a literários.
Foi o disco mais bem sucedido comercialmente da banda, muito graças a este dueto com a mega-estrela pop Kylie Minogue, uma australiana, tal como Cave. Este chegou mesmo a admitir que haveria muita gente chateada ao chegar a casa e ouvir o disco, percebendo que o single não era exemplificativo do seu som. O sucesso foi tal que Cave foi nomeado para personalidade masculina do ano, pela MTV, estação que passou constantemente o óptimo vídeo deste single. Cave acabou por solicitar ser retirado de entre os nomeados, o que acabou por acontecer.