התייחסו לקטע הבא ואז ענו על השאלה שאחריו באותה שפה כמו הקטע:  בספטמבר 1993, מדונה יצאה לסיבוב ההופעות העולמי "The Girlie Show World Tour", שבו היא התלבשה כדומינאטריקס מקרקת חוטים מוקפת רקדניות עירומות. בפוארטו ריקו היא רססה את דגל האי בין רגליה על הבמה, מה שגרם לזעם בקרב הקהל. במרץ 1994, היא הופיעה כאורחת בתוכנית "The Late Show with David Letterman", בה השתמשה בבלבול שדרש צנזורה בטלוויזיה, ונתנה ללטרמן זוג תחתונים שלה וביקשה ממנו להריח אותם. שחרור הספר, האלבום והסרט הסקסיים שלה, והופעתה האגרסיבית בתוכנית "לטרמן" גרמו למבקרים לפקפק במדונה כמתרוממת מינית. ביקורת ואוהדים הגיבו באופן שלילי, שאמרו כי "היא הלכה רחוק מדי" וכי הקריירה שלה הסתיימה. הביוגרף ג'יי רנדי טארבורלי תיאר את הבלדה שלה "אני אזכור" (1994) כניסיון להנמיך את הדימוי הפרובוקטיבי שלה. השיר הוקלט לסרטו של אלק קשישיאן "עם כבוד". היא עשתה הופעה שקטה עם לטרמן בתערוכת פרסים והופיעה בתוכנית The Tonight Show עם ג'יי לנו לאחר שהבינה שהיא צריכה לשנות את הכיוון המוזיקלי שלה כדי לשמור על הפופולריות שלה. עם אלבום האולפן השישי שלה, Bedtime Stories (1994), מדונה השתמשה בדמות רכה יותר כדי לנסות לשפר את תפיסת הציבור. האלבום הופיע לראשונה במקום השלישי ב-Billboard 200 וגרם לשני להיטים בחמישה הגדולים בארה"ב, "Secret" ו"Take a Bow", האחרון בראש ה-Hot 100 במשך שבעה שבועות, התקופה הארוכה ביותר של כל סינגל של מדונה. משהו לזכור, אוסף של בלדות, יצא בנובמבר 1995. האלבום כלל שלושה שירים חדשים: "You'll See", "One More Chance", ו-cover של "I Want You" של מרווין גיי. בערך באותה תקופה, מדונה החלה לצאת עם הראפר טופאק שאקור, אבל זה נגמר ב-1994. בשנה שלאחר מכן, שאקור חשף במכתב למדונה שהוא סיים את מערכת היחסים כי היא הייתה לבנה. מאוחר יותר היא נכנסה למערכת יחסים רומנטית עם מאמן הכושר קרלוס ליאון. ב-1996 מיוזיקל, Evita, מדונה שיחקה את התפקיד הראשי של אווה פרון. במשך זמן רב, מדונה רצתה לנגן...  שאלה: מה קונר אמר על מדונה?
מדונה שוב מבלבלת את הציפיות שלנו.