Niezwykle przejmującą rolę Magdalena Cielecka wykreowała w przedstawieniu 4.48 Psychosis Sarah Kane w reżyserii Grzegorza Jarzyny (koprodukcja warszawskiego Teatru Rozmaitości i Teatru Polskiego w Poznaniu, 2002). Doskonale pokazała studium autodestrukcji, powolnego zmierzania ku śmierci. Przez wiele lat sztuka grana była w Polsce i za granicą, a rola Cieleckiej nieustannie zbiera pochwały. Po premierze w St. Ann's Warehouse na Brooklynie w 2014 roku, Ben Brantley napisał w „New York Times”:
Zaadaptowana i wyreżyserowana przez Grzegorza Jarzynę, ta polskojęzyczna (i wykraczająca poza język) produkcja zmusza publiczność do bezwarunkowego zaangażowania w zgubny, prywatny spektakl autodestrukcji. „Popatrzcie na mnie” – mówi bezimienna bohaterka, bezkompromisowo i z oddaniem zagrana przez znakomitą Magdalenę Cielecką. „Dotknijcie mnie”. Jej słowa są tylko drwiną, wszak nie jesteśmy w stanie sięgnąć jej w oddali.
Na deskach warszawskiego teatru Rozmaitości Cielecka kontynuowała także współpracę z Krzysztofem Warlikowskim, u którego w 1999 roku zagrała Ofelię w Szekspirowskim Hamlecie. W 2003 roku wcieliła się w postać Ariela – tragicznego buntownika z Burzy Szekspira. Natomiast w Dybuku Szymona Anskiego i Hanny Krall (2003) zagrała Leę oraz żonę Adama S., pokazując głęboki, duchowy wymiar miłości. W Teatrze Telewizji można ją było oglądać jako m.in. Elmirę w sztuce Moliera Tartuffe czyli obłudnik w reżyserii Andrzeja Seweryna (2002) i Michelle w Komedii na dworcu Samuela Benchetrita w reżyserii Witolda Adamka (2004). Zagrała również w Piaskownicy Michała Walczaka w reżyserii Dariusza Gajewskiego (2005), świetnie sportretowała Stellę w Kolekcji Harolda Pintera, spektaklu telewizyjnym Marcina Wrony (2006). W 2008 roku Magdalena Cielecka zdobyła nagrodę Herald Angel Award na Festiwalu w Edynburgu. Została uhonorowana za role w spektaklach 4.48 Psychosis i Dybuku.
Po sukcesie Pokuszenia długo czekała na następną ciekawą rolę filmową. W Amoku Natalii Korynckiej-Gruz (1998) rozgrywającym się w nowopowstałym w Polsce środowisku maklerów giełdowych zagrała femme fatale, w kolejnym filmie Barbary Sass (Jak narkotyk, 1999) wcieliła się w postać śmiertelnie chorej, wrażliwej poetki, w romantycznej komedii Piotra Wereśniaka Zakochani (2000) była piękną i bardzo wyrachowaną modliszką żyjąca na koszt cudzych uczuć, w "Egoistach" Mariusza Trelińskiego (2000) zagrała ekscentryczną i histeryczną niedoszłą samobójczynię, a w Listach miłosnych Leszka Wosiewicza (2001) zagubioną emocjonalnie współczesną sobie rówieśniczkę. W Trzecim Jana Hryniaka (2004), filmie o młodym małżeństwie próbującym odbudować związek, wcieliła się w postać Ewy, w roli jej męża Pawła wystąpił Jacek Poniedziałek. Inną trzydziestoletnią mężatkę, pozornie spełnioną kobietę, także Ewę, która pragnie uczuć i coraz bardziej przybliża się do zdrady zagrała w S@motności w sieci Witolda Adamka (2006). Można ją było również oglądać w rolach: Hanny von Bronheim w Chaosie Xawerego Żuławskiego (2005), Emilii w Po sezonie Janusza Majewskiego (2006), Hanny w Palimpseście Konrada Niewolskiego (2006), Agnieszki, siostry porucznika Baszkowskiego w Katyniu Andrzeja Wajdy (2007) i Joanny w Wenecji Jana Jakuba Kolskiego (2010).
W grudniu 2015 miała premierę musicalowa baśń Agnieszki Smoczyńskiej Córki dancingu, w której Cielecka wcieliła się w postać artystki scenicznej o pseudonimie Boskie Futro. Zagrała także Izę, jedną z bohaterek Zjednoczonych stanów miłości, filmu Tomasza Wasilewskiego nagrodzonego Srebrnym Niedźwiedziem 66. Międzynarodowego Festiwalu Filmowego w Berlinie. Krytyk Nick James, wręczając reżyserowi nagrodę, mówił:
Jury było pod wielkim wrażeniem tej opowieści o czterech kobietach, które wierzyły w ideę lepszego życia w kraju w czasie wielkiej zmiany. Opowieści, która jest jednocześnie niezwykłym popisem aktorek, ich siły i nadziei.
W 2017 roku wcieliła się w kuratorkę warszawskiego Muzeum Sztuki Nowoczesnej, Natalię Sielewicz, w filmie Serce miłości Łukasza Rondudy i matkę głównego bohatera dramatu Najlepszy Łukasza Palkowskiego.
