In 1991, solista a lansat primul sau film documentar: „Truth or Dare, cunoscut si sub numele „In pat cu Madonna, regizat de Alek Keshishian. In documentarul care i-a adus Madonnei 15 milioane de dolari, apar scene alb-negru din culisele turneului „Blond Ambition si imagini color din concertele propriu-zise. In acelasi an, artista a primit un rol in filmul „Liga feminina de baseball si a lansat melodia „This Used to Be My Playground. A inceput o relatie cu solistul Vanilla Ice, despre care a vorbit in cartea sa erotica „Sex (book) lansata in 1991. Aceasta continea fotografii realizate de Steven Meisel, in care Madonna aparea in diverse pozitii sexuale. Solista a fost aspru criticata de presa, dar cartea a fost o campanie perfecta de lansare a noului sau album „Erotica. Intre 1992 si 1993, Madonna a avut mai multe relatii pasagere: cu actorul John Enos, cu bodyguardul sau, Jim Albright, si cu baschetbalistul Dennis Rodman. In 1993, in concertele din cadrul „The Girlie Show Tour, Madonna aparea imbracata in piele, alaturi de dansatoare topless. Ea a starnit un imens scandal in Puerto Rico: si-a infasurat steagul insulei intre picioare. In aceasta perioada „sexuala din cariera sa, ea a lansat albumul „Bedtime Stories. Materialul discografic a inclus piesa scrisa de rapper-ul Babyface, „Take a Bow. Videoclipul realizat de Michael Hussman avea sa o ajute mai tarziu pe Madonna sa obtina rolul principal in „Evita. Filmul a fost lansat in 1996 si continea hitul „Dont Cry for Me Argentina, compus special pentru aceasta productie cinematografica si piesa „You Must Love Me, care a castigat Premiul Academiei si un Glob de Aur pentru cea mai buna coloana sonora. Madonna a mai fost recompensata cu un Glob de Aur pentru Cea mai buna actrita intr-un film muzical. Dupa succesul inregistrat cu filmul „Evita, solista si-a exprimat intentia de a realiza un film despre viata pictoritei Frida Kahlo. Ea isi dorea ca Marlon Brando sa joace rolul lui Diego Riva. Acest proiect avea sa fie realizat insa de catre Salma Hayek.
In acelasi an, Madonna si-a lansat primul album Greatest Hits, „The Immaculate Collection, care includea si doua cantece noi: „Rescue Me si „Justify My Love. Videoclipul ultimei melodii a scandalizat o lume intreaga. El a fost filmat intr-un hotel parizian si continea scene erotice, sado-masochiste dintre solista si iubitul sau de atunci, Tony Ward. Cei doi au inceput sa se intalneasca dupa o scurta relatie a Madonnei cu Lenny Kravitz. Tony Ward era model si actor de filme porno si mai aparuse si in alte videoclipuri ale Madonnei, precum „Cherish sau „Justify My Love. Videoclipul nu a fost difuzat la MTV.
In 1996, Madonna l-a intalnit pe Carlos Leon, in timp ce se plimba prin Central Park. El a devenit antrenorul personal, dar si iubitul ei. Pe 14 octombrie, Madonna a nascut-o pe Lourdes Maria (Lola) Ciccone Leon. Fetita a fost numita Lourdes, dupa oraselul din Franta pe care mama sa a vrut sa-l viziteze, dar nu a mai reusit. Se pare ca, in anul 1885, credinciosii au putut-o vedea acolo pe Fecioara Maria. In 1997, Madonna a pus punct relatiei sale cu Carlos Leon. Un an mai tarziu, ea a lansat albumul „Ray of Light, care a obtinut de patru ori discul de platina si patru premii Grammy. Acesta a fost considerat cel mai complet album al sau dupa care Madonna a scris un single pentru coloana sonora a filmului „Austin Powers 2: Spionul care mi-a tras-o.