Kościół pw. Nawiedzenia Najświętszej Marii Panny w Trokach często jest nazywany świątynią Witoldową, gdyż ufundował go w 1409 r. książę Witold. W czasach średniowiecza kościół pełnił też funkcje obronne i był otoczony fosą, przebudowywano go w XVII i XVIII w.
W kościele Witoldowym znajduje się cudowny obraz Matki Boskiej Trockiej z Dzieciątkiem, namalowany na 4 deskach w drugiej połowie XVI w. Jest to najstarszy koronowany na Litwie obraz, koronacji którego w 1718 r. dokonał biskup wileński Konstanty Brzostowski.
Pielgrzymowanie do Trok rozpoczęto na początku XVII w. , pierwsza pielgrzymka wyruszyła w 1604 r. z Wilna, na czele z biskupem Wojną , Madonnę Trocką proszono o opiekę nad Litwą opanowaną przez dżumę i głód. Po modlitwach pielgrzymów morowe powietrze ustąpiło.
Bardzo dużo pielgrzymek do Trok organizowali w XVII - XVIII w. jezuici w ramach walki z reformacją.
W 1700 r. przy kościele dobudowano kaplicę Romerów, znanego na Litwie rodu, który posiadał majątki także w okolicach Trok. Wielu przedstawicieli Romerów spoczywa w podziemiach świątyni.