Charakterystyczne masywne dwie wieże świątyni, połączone słynnym Mostkiem Pokutnic (czy też jak niektórzy wolą Mostkiem Czarownic) stanowią nieodłączny element panoramy miasta. Kościół św. Marii Magdaleny należy do najstarszych i najpiękniejszych przykładów architektury sakralnej we Wrocławiu doby gotyku. Obecna budowla powstała w XIV w. Badania archeologiczne wykazały jednak, że już co najmniej od XII w. istniała tu romańska świątynia.

Obecnie wnętrze kościoła jest surowe i niemal całkowicie pozbawione dawnego średniowiecznego wystroju. Gotycki ołtarz został przekazany do kościoła św. Bartłomieja na Ostrowie Tumskim. Świadectwem tamtej epoki są: XIV wieczne sakramentarium, kapliczka ze sceną Ukrzyżowania z 1491 r., fragmenty polichromii na łuku tęczowym oraz kilka detali architektonicznych.

Sakramentarium powstało około 1375-80. Zabytek zdobią przedstawieniami Męki Pańskiej i Zmartwychwstania, oraz znajdujący w zwieńczeniu pelikan, karmiący pisklęta własną krwią, spływającą z piersi.
Kapliczka ze sceną Ukrzyżowania powstała na zlecenie Rady Miejskiej. Pierwotnie znajdowała się na rogu ulic Marii Magdaleny i Łaciarskiej. Miała ona przypominać o skazaniu na śmierć za zdradę patrycjusza Heinza mł. Dompniga, poplecznika Macieja Korwina króla Węgier. Karę wykonano przed ratuszem. Było to niecodzienne wydarzenie. Zwykle kary śmierci wykonywano w okolicy kościoła Bożego Ciała (ścięcie mieczem) lub za murami miasta (szubienica).
Pozostała część obecnego wystroju świątyni pochodzi z późniejszych czasów. Do najcenniejszych należy barokowa Grupa Ukrzyżowania w ołtarzu głównym, manierystyczna ambona oraz liczne nowożytne epitafia i płyty nagrobne.
Gotyckie retabula, rzeźby i obrazy podzieliły losy średniowiecznych dzieł sztuki pochodzących z innych wrocławskich świątyń (o tym wyżej).

Bartolomäus Stein, XVI-wieczny geograf śląski, podaje, że wnętrza kościoła kryły w tamtym czasie pięćdziesiąt osiem gotyckich ołtarzy. Do naszych czasów zachowały się we fragmentach Poliptyk Złotników Wrocławskich oraz Poliptyk Kuśnierzy Wrocławskich, płaskorzeźba św. Łukasza malującego w komnacie Madonnę (środkowa część retabulum z Kaplicy Malarzy), fragmenty Tryptyku św. Stanisława 1508-9 z Kaplicy Złotników, szafa nastawy św. św. Katarzyny, Barbary i Małgorzaty, rzeźba Marii z Dzieciątkiem na sierpie księżyca z Ołtarza Mariackiego z Kaplicy Złotników (na temat wystroju Kaplicy Kuśnierzy i Kaplicy Złotników odrębny wpis poniżej). Zabytki te znajdują się obecnie w Muzeum Narodowym we Wrocławiu. Spośród średniowiecznego wystroju kościoła ocalało do naszych czasów kilkanaście rzeźb i kilka epitafiów, także przechowywanych dziś w Muzeum Narodowym we Wrocławiu.
Spośród rzeźb najbardziej okazałe są XIV-wieczne figury św. Marii Magdaleny i Apostołów, pochodzące z Pracowni Mistrza Figur Apostołów oraz Grupa Drogi na Golgotę, wykonana około 1500r. w Pracowni Wrocławskiej.

Osobną kwestię stanowi Veraikon, należący dziś do zbiorów Muzeum Narodowego w Warszawie. Veraicon (od łacińskiego vera icon czyli prawdziwy obraz) utrzymany jest w duchu tradycji bizantyjskiej. Oblicze Chrystusa, „nie malowane ludzką ręką”, jest spokojne, statyczne, pozbawione wyrazu bólu i cierpienia. Dzieło wykonano ok. 1400r. Veraikon trafił do kościoła Marii Magdaleny dopiero w 1727 r., z daru spadkobierców słynnego renesansowego ogrodu, założonego we Wrocławiu pod koniec XVI w. przez Laurentiusa st. Scholtza von Rosenau.