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