Pierwszy kościół na wysepce powstał już w XV wieku, choć jego rozmiary były skromne. Dopiero wraz z rozbudową wyspy zdecydowano się na budowę nowej większej świątyni. Kościół Matki Boskiej na Skale wybudowano w 1630, a w 1. poł. XVIII w. dobudowano do niego okrągłą dzwonnicę.
Wnętrze kościoła jest bogato zdobione. Główny, marmurowy ołtarz, powstał w 1765 jako dzieło duetu z Genui: Antonio i jego syna Gerolamo Capellano. Budowę ołtarza sfinansowała cała społeczność Perastu. Plany jego budowy powstały w Wenecji, skąd zostały wysłane do Genui przez kapitana Mato Chiorko (Čorko). Ołtarz przywiózł do Perastu w 1796 kapitan Josip Rupčić na statku Corriere di Soria. W środku ołtarza znajduje się tabernakulum z zielonymi marmurowymi filarami, zwieńczone baldachimem, z niszą zawierającą gotycki, uważany za cudowny, obraz Matki Boskiej z Dzieciątkiem. Po bokach obrazu znajdują się marmurowe figury św. Jana Ewangelisty z orłem i Biblią oraz św. Rocha z psem i laską. Rzeźbił je Francesco Gai – syn Antonia Gai, zaś budowę ich zlecił Ivan Diego Marinović w 1783. Wnętrze kościoła (na ścianach bocznych i suficie) pokrywa 68 barokowych obrazów olejnych Tryfona (Tripo) Kokolji z Perastu. Sufit jest udekorowany scenami z życia Maryi i Chrystusa, a także ewangelistów.