Найстаріша церква в місті — Пр. Богородиці була збудована в давньому Сокалі на лівому березі ріки Бугу і була знищена під час татарського наскоку у 1519 р. Після перенесення міста на правий берег тут збудовано нову церкву того ж храму, яка згоріла під час пожежі міста у 1821 р. Візитація 1749 р. холмського єпископа Феліціяна Володкевича подає: «... церква дерев`яна в стінах і дахах добра, з трьома дверима на залізних завісах...». Поруч з нею була споруджена на початку XVI ст. мурована церква св. Миколи. Обидві, обведені спільним муром, творили монастирський комплекс. Відновлювалася церква св. Миколи у 1613 та 1677 рр., реставрувалася, як свідчить напис над хорами, у 1694 р. У 1594 р. при церкві відбувалися наради в присутності перемиського єпископа Михайла Копистинського про справи унії. В XVII ст. при ній проживав Гавриїл Коленда, митрополит Київський і Галицький, протоархімандрит василиян, який у 1669 р. подарував церкві образ «Пр. Богородиці». Про перебудови споруди першої половини XVIII ст. свідчить акт візитації 1731 р.: «Сама церква мурована, з давніх давен не була крита зверху, але тільки засклеплена, тепер одначе кришею і банею високою украшена». У 1752 — 1756 рр. розписана, ймовірно, С. Строїнським. Під час обнови за о. Івана Ціпановського (1853 — 1877) наново розмальована, встановлений новий іконостас. У 1927 р. проведе¬на чергова віднова споруди. Ушкоджена під час другої світової війни, замкнена по її за¬кінченні. Реставрована з максимальним відновленням первісного вигляду за проектом архітектів Ігоря Старосольського та Валентини Пашиної у 1971 —1975 рр. і перетворена на міський краєзнавчий музей. ~2~ Церква тридільна, з еліпсоїдними вівтарними апсидами (північна перебудована на прямокутну), первісно мала три бані над кожним об`ємом і дві менші над апсидами (над північною не збереглась), є пам`яткою української архітектури доби Ренесансу.
~3~ З 1989 р. знову служить громаді.