 Directed by British artist Chris Cunningham , the music video for " Frozen " was filmed at Cuddeback Lake within the Mojave Desert in California during January 7 – 11 , 1998 . Madonna thought that there are a lot of magical , mystical powers in the desert and that it is a magical place to be . It was inspired by the film The English Patient and Martha Graham 's work . The music video premiered on February 16 , 1998 on MTV at 4 p.m. The black goth gown outfit Madonna wears on the video was designed by Olivier Theyskens , and provided by then @-@ new collaborator , designer Arianne Phillips . In an interview with MTV News , Cunningham stated about his work with Madonna , saying that he thought Madonna became interested to work with him after seeing his Aphex Twin @-@ directed music video , " Come to Daddy " ( 1997 ) . Madonna stated that she and her team thought of filming the video in Iceland , as the idea to the video was to go someplace cold and where there is snow , but declined the idea . She thought : 
