Trakų Švč. Mergelės Marijos Apsilankymo bažnyčios statybą 1409 m. fundavo Lietuvos didysis kunigaikštis Vytautas. Gotikinė bažnyčia buvo pastatyta apside į rytus ir pritaikyta miesto gynybai. Senasis, pagrindinis įėjimas į bažnyčią buvęs šiaurės pusėje, t. y. nuo Pusiasalio pilies. XV a. bažnyčia buvo dekoruota bizantinio stiliaus freskomis, kurių fragmentus, atidengtus 2006 m., galima pamatyti ir dabar.

Trakų bažnyčia apniokota per 1654-1667 m. Lenkijos-Lietuvos karą su Rusija ir Šiaurės karo metu XVIII a. pr. Iki 1718 m. trukusių atstatymo ir rekonstrukcijos darbų metu ji įgavo baroko bruožų.

Tuo pačiu metu buvo sukurtas ir didysis barokinis altorius su skulptūromis, gipsatūromis. 1794 m. sukilimo metu degusią bažnyčią vėl restauravo 1796 m., ne kartą ji remontuota XIX a. Pastatas nukentėjo ir pasaulinių karų metu. Paskutinį kartą bažnyčia restauruota 2008 m.

Prie bažnyčios yra 1700 m. Mato Riomerio iniciatyva pristatyta koplyčia, kuri tapo giminės mauzoliejumi. Čia yra ir dailininko Alfredo Riomerio kapas (1832 - 1397 m.).

Trakų Bažnyčia garsėja stebuklingu, seniausiu Lietuvoje, Dievo Motinos paveikslu. Legenda sako, kad 1123 m. Konstantinopolyje nutapytą Dievo Motinos paveikslą 1390 m. Vytautui Didžiajam padovanojo Bizantijos imperatoriaus Emanuelis II Paleologas, o 1409 m. Vytautas Didysis paveikslą padovanojo Trakų bažnyčiai.

Paveikslas greitai pradėjo garsėti stebuklais. Į Trakus pradėjo keliauti maldininkai net iš ukrainiečių, gudų, prūsų žemių, o Trakų Dievo Motina imta laikyti ypatinga Lietuvos globėja. Stebuklais garsėjantį paveikslą 1718 m. Romos popiežius Klemensas XI vainikavo auksine karūna. 1718-1783 m. laikotarpyje Trakuose užregistruoti 42 nauji stebuklai, vėliausi - 1902 m. Šiandien stebuklingąjam paveikslui, puošiančiam didįjį altorių, tebeaukojami padėkos ženklai.