El cantante australianu Nick Cave amosóse bien interesáu por trabayar con Minogue dendel llanzamientu de Better the Devil You Knowdiciendo que contién «una de les lletres más angustiantes y violentes na música pop», y «cuando Kylie Minogue canta estes pallabres, hai una inocencia a ella que fai que lhorror desta lletra respigante sía entá más convincente». Ella collaboró en «Where the Wild Roses Grow» (1995), una trabancosa balada que les sos lletres narra lasesinatu dende los puntos de vistes del asesín (Cave) y la so víctima (Minogue). El video tuvo inspiráu pola pintura Ofelia de John Everett Millais, y amosó a Minogue como la víctima asesinada, llexando nun estanque mientres una culiebra nada sobrel so cuerpu. El senciellu recibió una estensa atención nEuropa, onde algamól top 10 en dellos países, y aclamación nAustralia onde algamól númberu dos nos gráficos de senciellu, y ganó un premiu ARIA por cantar del añu» y «meyor llanzamientu pop». Nes siguientes apaiciones de conciertu con Cave, Minogue recitó la lletra de «I Should Be So Lucky» como una poesía nel «Poetry Jam» nel Royal Abert Hall, Londres por suxerencia de Cave, y más tarde describir comol «momentu más catárticu». Ella acreditó a Cave con da-y lenfotu pa espresase artísticamente, diciendo: «Él enseñóme a nun esviase demasiáu de lo que soi, sinón dir más allá, probar coses distintes, y nunca perder de vista a mi fueru internu, la parte más difícil foi desamarrar el mio verdaderu yo y ser totalmente sincera na mio música». Por 1997, Minogue tuvo nuna rellación col fotógrafu Stéphane Sednaoui, quien la animo a desenvolver la so creatividá. Inspiráu pola cultura xaponesa, ellos crearon una combinación visual duna superheroína geisha y manga» pa les fotografíes del álbum Impossible Princess y el video pa «German Bold Italic», la collaboración de Minogue con Towa Tei. Minogue dibuxó la so inspiración dende la música dartistes como Shirley Manson, Garbage, Björk, Tricky y U2, y músicos xaponeses como Pizzicato Five y Towa Tei. 