דייוויד בראון מאנטרטיינמנט ויקלי תיאר את השיר כ"מלודרמה מטלטלת שלעיתים קרובות עוצרת נשימה". צ'אק ארנולד מאנטרטיינמנט ויקלי כתב: "[השיר] נשמע לא דומה לשום דבר שמדונה אי-פעם עשתה קודם לכן; היא יוצרת [בו] יער מיסטי של פליאה קולית – עם מנגינת כלי מיתר סוחפת – ל-'Frozen' יש מגינה כמעט אופראית שלעולם לא מצליחה לגרום לך צמרמורת". סטיבן תומפסון מ-"The A.V. Club" כתב, "'Frozen' האטמוספירי הוא סינגל מוביל נהדר על אף מילים כמו, 'אהבה היא ציפור / היא צריכה לעוף'". לעומת זאת, ב-"NME" כינו את השיר "עוד ערימה מהשירים הישנים והבכיינים שלה". ג'ים פרבר מדיילי ניוז כתב ש-"Frozen" מתפשרת על הסגנון האלקטרוני שלו עם "יותר מדי פופ פושר". קרוליין סאליבן מגרדיאן ביקורת אותו בשליליות. חוסה פ. תומאס מ-"AllMusic" דירג את השיר בשני כוכבים מתוך חמישה, ותיארו אותו כ"קריר".
תשבחות.
בשנת 2003, מעריציה של מדונה התבקשו להצביע עבור "20 הסינגלים המובילים של מדונה בכל הזמנים", על ידי מגזין "Q". "Frozen" דורג במקום העשירי ברשימה. במגזין בילבורד דירגו את "Frozen" במקום ה-25 ברשימת "40 הלהיטים הגדולים ביותר של מדונה", וקבעו שהשיר סימן "שינוי קולי" בקריירה של מדונה. ברולינג סטון דירגו גם כן את השיר כשירה השישי הטוב ביותר של מדונה בכל הזמנים על פי סקר קוראים, ואמרו כי השיר מגיע ל"איזון המושלם בין נגישות לפופ, בלדרי מתוחכם וטקסטורות אלקטרוניות חדשניות". מארק גרהאם מ-"VH1" כלל את "Frozen" ברשימת השירים האהובים עליו ביותר של מדונה, ודירג אותו במקום ה-36; את הרשימה פרסם לכבוד יום הולדתה ה-53 של הזמרת. במאי 2018, דירגו במגזין את השירים המובילים של 1998, וברשימה כללו את "Frozen" במקום ה-31. פרנק דיג'קומו מטעם המגזין טען שהלחן שלו הציג "מדונה חכמה יותר, בוגרת יותר, אחת שעדיין שולטת בקריירה שלה". בעת דירוג הסינגלים של מדונה, לכבוד יום הולדתה ה-60, ג'וד רוג'רס מטעם הגרדיאן מיקמה את "Frozen" במקום השביעי. היא כתבה: "מדובר בשיר אמביינטי, אפל ותזמורתי והוא בעל מצב רוח שבו מדונה מצטיינת. 'Frozen' משלב בצורה מדהימה את הטמפרטורות השונות של הפופ של שנות ה-90 – מעין שילוב צלילי ההפקה האלקטרונית הקרה של ויליאם אורביט עם החום המאובק והקולנועי של הלחן וכלי המיתר הצפון אפריקאיים". באוגוסט 2018, אנטרטיינמנט ויקלי הכתירו אותו לסינגל ה-18 הטוב ביותר של הזמרת. ברשימת "100 השירים הטובים ביותר בכל הזמנים של מדונה" שפורסמה ב-"Parade", דורג "Frozen" במקום ה-22. ברשימה דומה "Smooth Radio" של דורג השיר במקום השני.
וידאו קליפ.
הקליפ של "Frozen" צולם באגם קודבק; אגם יבש במדבר מוהאבי (קליפורניה), בבימויו של במאי הווידאו קליפים האנגלי כריס קנינגהם. שאר הצוות כלל את ניקולס ד. ורטל שהיה אחראי על סצנות הכלב השחור, דריוס קונג'י (שעבד עם מדונה ב-"Fever" (1993) ופסקול הסרט "אוויטה") כצלם, גארי נייט כעורך, פיטר סאביץ' כמעצב התסרוקות, ג'ואן גייר כמאפרת, ג'ון פיין בפוסט-פרודקשן וסטיב מרגטרויד, דן ויליאמס, סטיב הייאם ואנתוני ולשם על האפקטים מיוחדים. מדונה החלה להתעניין בשיתוף פעולה עם קנינגהם לאחר שהתרשמה מעבודתו על "Come to Daddy" (1997) של המוזיקאי והדי ג'יי אפקס טווין, והעירה שיש לו "רגישות אפלה מאוד", שמושכת ומעניינת אותה. הוא הצהיר שזו הייתה ההתנסות הראשונה שלו עם אמן "גדול", והסביר שהתנהל משא ומתן אודות התקציב העתיר של הקליפ. עם זאת, הוא הצהיר שהקליפים שלה הם שהובילו אותו להמשיך בקריירה כבמאי; בהקשר זה הוסיף: "יש לי חיבה גדולה כלפי הקליפים של מדונה שיצאו במרוצת השנים, 'הם מבריקים'. אני זוכר שראיתי את זה של "Rain" (1993) כשהייתי קצת יותר צעיר וחשבתי שזה יפה. ממש מפואר".
הצילומים נמשכו ארבעה ימים, בין 7 ל-10 בינואר 1998. עבור קנינגהם, הדבר החשוב ביותר בצילומים היה להתרכז בתדמיתה של מדונה. כלומר, איך היא הייתה נראית ומוצגת, כמו גם העברת המסר של הקליפ ואיך שהוא נראה, הן מבחינת צבעיו הקרים שנטו לגוון ירוק-כחול והן מבחינת הקונספט המעורפל שלו. הוא ציין שמדונה אפשרה לו לבטא את החזון האמנותי שלו מבלי שהתערבה והוסיף: "צילומי הקליפ של "Frozen" היו די טובים. היא [מדונה] בהחלט אוהבת לביים ולחלק הוראות, אך [היא] נותנת לבמאים לעשות את העבודה שלהם מבלי להתערב בחזונם האמנותי". הוא השתמש בטכנולוגיית מורפינג כדי ליצור כמה סצנות מסוימות, כולל צילום שבו מדונה נופלת וכשהיא פוגעת בקרקע, הופכת ללהקת עורבים.
מדונה הביעה שברצונה לצלם את הקליפ במדבר, כיוון שזהו מקום עם "כוחות מיסטיים רבים" ו"קסום" להיות בו, בנוסף לכך שהוא מעורר "ייאוש ורוחניות". עם זאת, הרעיון ההתחלתי היה ללכת למקום שבו היה קר מאוד ויש שלג, אז היא חשבה לטוס לאיסלנד, אך בהמשך שינתה את דעתה והצהירה:
במהלך הצילומים התמודד הצוות עם בעיות נוספות, כמו גם עם הקושי של קנינגהם לביים כפי שרצה; בריאיון עם קלפה סאנה לניו יורק טיימס, הוא הסביר: "כל כך התרגשתי שסוף סוף יש לי תקציב עתיר לעשיית קליפ ברמה שכזו, ואז הגעתי למדבר וחווינו מונסון: ירד גשם על הציוד, המצלמות נשברו ובסופו של דבר ביימתי כשהייתי מכוסה בשמיכה, בתקווה שבשלב העריכה, נצליח לפתור את הכול". בנוסף לכך שחלק מהרעיונות שלו לא הצליחו להתממש בגלל הגשם בימים הראשונים, הוא היה מתוסכל מהעבודה הכוללת וזאת, כיוון שהוא רצה שהקליפ יהיה הרבה יותר משוכלל מבחינת האפקטים. בחוברת שצורפה ל-"DVD The Work of Director Chris Cunninghman" (2003), הוא הסביר שהרעיון המקורי כלל "ערימות עצומות של גופות במדבר", כמו גם הצגה של כמה וריאציות של מדונה, שהופכת ללהקת עורבים ולאחר מכן לכלבים. הוא תיאר אותו כ"קליפ עם ביצועים מרשימים ומשוכללים המציגים את מדונה במלוא תפארתה, כמו גם את התלבושת שלה וכל צורה אליה היא הפכה". יתר על כן, ציין שהאפקטים המיוחדים שבהם נעשה שימוש היו "באיכות ירודה" והעדיף שהצילומים האחרונים יתמקדו בביצוע ה"מיסטי והטמפרמנטלי" של מדונה. כתוצאה מהקשיים שחוו, הוא נשבע שלעולם לא יעבוד יותר עם אמנים גדולים.
"Frozen" הוכתר לקליפ המשודר ביותר בטלוויזיה בשנת 1998 ב-"MTV" אירופה. במהלך טקס פרסי הווידאו קליפים של MTV לשנת 1998 זכה בפרס בקטגוריית, "האפקטים הוויזואליים הטובים ביותר"; הפרס הוענק למרגטרויד, ויליאמס, ולשם והייאם. באותו הערב, זכתה מדונה בפרס הראשי בקטגוריית "קליפ השנה" עבור, "Ray of Light". בטקס פרסי MVPA לשנת 1999 הוא זכה בקטגוריה הזו גם כן, והועמד בקטגוריות "עיצוב השיער הטוב ביותר" (סאביץ'), "עיצוב האיפור הטוב ביותר" (גייר), "הצילום הטוב ביותר" (קונג'י) ו"הבימוי הטוב ביותר" (קנינגהם). בטקס פרסי CAD Week שאירע ב-1999, הוא הועמד בקטגוריות "קליפ הדאנס הטוב ביותר", "העריכה הטובה ביותר" (נייט) ו"האפקטים הוויזואליים הטובים ביותר".
הוא זכה להכרה כ"קליפ הבינלאומי של השנה" בטקס פרסי פורין והגיע למקום החמישי באותה הקטגוריה בטקס פרסי גפה. בנוגע לזכיותיו או העמדותיו לפרסים מרובים בקטגוריות "האפקטים הוויזואליים הטובים ביותר", אמר קנינגהם ללונדון טיימס: "אלוהים יודע למה. הקטגוריות [האלה] מטופשות. אם אני לא מרוצה ממשהו והוא זוכה בפרס, זה אומר לי שאחרים לא רואים את הדברים כמוני".
הצלחה מסחרית.
אמריקה.
"Frozen" צבר איירפליי רב ב-161 תחנות רדיו וב-28 בפברואר 1998, הופיע לראשונה במקום ה-31 במצעד שירי הרדיו עם 25.9 מיליון האזנות בסך הכול. בשבוע שלאחר מכן הוא צבר עלייה של 62% (שווה ערך ל-42 מיליון האזנות) ב-187 תחנות רדיו, ובעקבות כך דורג במקום ה-12 במצעד. עם יציאתו המסחרית ברחבי ארצות הברית, הוא נמכר בלמעלה מ-42,000 עותקים בשבעת הימים הראשונים ליציאתו; דבר שהוביל לכך שהוא דורג במקום ה-17 במצעד הסינגלים המסחריים של בילבורד וזאת, תוך שהופיע לראשונה במקום השמיני במצעד הבילבורד הוט 100 ב-21 במרץ 1998. במצעד הבילבורד הוט 100 היה "Frozen" לשירה השני של מדונה שהופיע לראשונה בעשירייה הפותחת, ובכך השתווה ל-"You'll See" שעשה זאת בדצמבר 1995. בנוסף, הוא הפך לשירה ה-36 שדורג ב-40 העליונים במצעד; המספר הרב ביותר של שירים לאישה אחרי הזמרת האמריקאית אריתה פרנקלין. כמו כן, מדונה הרחיבה את שיאה כאמנית הסולו עם מרבית השירים שדורגו בעשירייה הפותחת במצעד (31), כשרק הביטלס (34) ואלביס פרסלי (38) מלפניה. למעט 1988, מדונה הכניסה שיר לעשירייה הפותחת בכול שנה מאז 1984. שבועיים לאחר מכן (ב-4 באפריל באותה השנה), הוא דורג במקום השני מאחורי "All My Life" של הצמד האמריקאי קיי-סי &amp; ג'וג'ו, והפכה לאמן עם מרבית השירים שהגיעו למקום השני במצעד, עם שישה שירים בסך הכול – " (1985), " (1987), ", " (1989) ו-"" (1994) – ושברה את השוויון עם קרידנס קלירווטר רבייבל והקרפנטרז; בשנת 2019, הזמרת-יוצרת האמריקאית טיילור סוויפט השתוותה למדונה עם "You Need to Calm Down" מאלבום האולפן השביעי שלה, "Lover". לאחר ש-500,000 עותקים נשלחו לקמעונאים, ומאחר שמחציתן נמכרו עד 11 באפריל, ת'דה סנדיפורד-וולר מבילבורד הצהירה שאין סיכוי שהשיר יגיע למקום הראשון במצעד. אילו הייתה עושה זאת, היא הייתה משתווה לזמרת-יוצרת האמריקאית מריה קארי כאמנית עם מספר השירים הרב ביותר שהגיעו למקום הראשון במצעד (12). "Frozen" נשאר בסך הכול עשרים שבועות במצעד, ובסוף שנת 1998 דורג במקום ה-32.