Background and release
Since 1996, Madonna went through a number of "life-changing experiences" which included giving birth to her daughter Lourdes, gaining interest in Eastern mysticism and Kabbalah, as well as earning the title role on the film adaptation of the musical Evita (1996). A year later she started working on Ray of Light, her eighth studio album. Madonna wrote songs with William Orbit, Patrick Leonard, Rick Nowels and Babyface. The album would reflect the singer's changed perspectives about life. Author Carol Benson noted that it was a "deeply spiritual dance record", with the crux of it based on Madonna's career, her journey and the many identities she had assumed over the years. Motherhood had softened the singer emotionally, which was reflected in the songs. She started talking about ideas and used words which implied deep and personal thoughts, rather than the regular dance-floor anthemic tunes she had composed. The singer began introspecting herself with motherhood being a "big catalyst for me. It took me on a search for answers to questions I'd never asked myself before", she said to Q magazine.
Madonna worked primarily with Orbit after Guy Oseary, Maverick Records's partner, phoned Orbit and suggested that he send some songs to the singer. He sent a 13-track digital audio tape (DAT) to Madonna, and "Frozen" was among these tracks. "I was a huge fan of William's earlier records. [...] I also loved all the remixes he did for me and I was interested in fusing a kind of futuristic sound but also using lots of Indian and Moroccan influences and things like that, and I wanted it to sound old and new at the same time", Madonna said. The singer drew inspiration from Bernardo Bertolucci's 1990 British-Italian drama film, The Sheltering Sky, which dealt with a couple trying to save their marriage during a trip to Africa. She wanted to have the "whole Moroccan/orchestral/super-romantic/man-carrying-the-woman-he-loves-across-the-desert vibe" for the track. Still continuing work with Leonard on some of the tracks, Madonna asked him to give her a composition with "tribal feel, something really lush and romantic". They composed the melody on the DAT and recorded the demo, which stretched to over 10 minutes due to Madonna continuing writing the track.
A low quality snippet of "Frozen" was leaked by fans on January 23, 1998, after it debuted on radio in Singapore, and posted it on the Internet. They said they knew what they were doing was wrong, but that they hoped it would simply generate interest from Madonna. The song was played on the US radios, including the WKTU New York radio. Warner Bros. Records enlisted the Recording Industry Association of America (RIAA)'s Anti-Piracy Unit to delete the Internet downloads of the song. Erik Bradley, musical director of Chicago B96, classified "Frozen" as a "the mark of a smash. Clearly, American pop radio needs Madonna", after he played the track on his station. According to Jon Uren, marketing director of Warner Music Europe, the song also had "fantastic" early support across Europe. Shortly after the song leaked, a remix version of "Frozen" was broadcast by the BBC website, and also was previewed on the soundtrack at the 1998 Versace fashion spring parade. The single was released commercially on February 23, 1998 in the United States.