Trudno jednoznacznie stwierdzić od kiedy w Sokołowie Podlaskim zaczęła funkcjonować Cerkiew wschodnia. Z historycznego podziału miasta na część ruską i lacką wynika, że każda ze społeczności, zapewne posiadała swoją świątynię już w wieku XV.
O parafii greckiej wiemy, że funkcjonowała na pewno w XVI wieku, kiedy właścicielami dóbr była od 1508 roku (po Sepieńskim i Sokołowskich) można rodzina Kiszków. Według tradycji przekazanej przez źródła prawosławne w wieku XVI posługę przy cerkwi sokołowskiej pełnili mnisi prawosławni z Brześcia i Drohiczyna. Równie mało wiadomo o czasie i okolicznościach przyjęcia unii brzeskiej przez Cerkiew sokołowską. Podobno unię przyjął w 1614 roku ówczesny świeszczennik Jan Zalewski (który wcześniej był wikarym w Siemiatyczach), następnie zaś w 1621 roku znowu powrócił do prawosławia. Jako prawosławna wzmiankowana jest parafia sokołowska w połowie XVII wieku. Cerkiew funkcjonowała na tzw. Ruskim Mieście, na wzgórzu między dzisiejszymi ulicami Długą, Siedlecką i Repkowską i nosiła wezwanie Protekcji Najświętszej Maryi Panny. W tej części miasta posesję swoją miał też pop ruski.
Od Radziwiłłów w drugiej połowie XVII wieku dobra sokołowskie przeszły do możnej rodziny Krasińskich. Wtedy też zapewne wprowadzono tu unię. W 1716 roku Jan Bonawentura Kasiński, wojewoda płocki nadał beneficjum sokołowskie parochowi sokołowskiemu ojcu Józefowi Ilkiewiczowi. To właśnie z czasów duszpasterzowania w Sokołowie Józefa Ilkiewicza pochodziła najstarsza wizytacja cerkwi sokołowskiej dokonana w 1726 roku, kiedy właścicielem dóbr był Błażej Krasiński, kasztelan płocki, wnuk Jana Bonawentury (zm. 1717) a syn Stanisława Bonifacego (zm1717): Cerkiew kiedyś była drewnianą strukturą, lecz teraz do szczętu zgniła, przecież pod dachem aczkolwiek trzymającym się, gontowym. Kopuła sama opadnie, jeszcze jednak z krzyżem wielkim żelaznym. Dzwonnica osobno stojąca z bramą i dwoma rezydencjami nowa, pod dachem gotowym z krzyżem żelazny.
W cerkwi był ikonostas i wiele elementów wskazujących na tradycję wschodnią (ikonostas, carskie wrota itp.). Zupełnie inna sytuacja była w 1757 r., kiedy sporządzono kolejną wizytację. W tym czasie kolatorem cerkwi i właścicielem Sokołowa był Tadeusz Lipski, kasztelanic łęczycki, późniejszy kasztelan łęczycki, generał-lejtnant, komediopisarz (zm. 1796) a administratorem cerkwi ojciec Samuel Filanowicz. W tym czasie wyposażenie cerkwi praktycznie nie różniło się od kościoła katolickiego (ołtarze, brak ikonostasu, konfesjonały, chór). Podobne informacje o cerkwi i jej wyposażeniu przynosiła wizytacja sporządzona w 1789 roku kiedy właścicielem miasta i dóbr sokołowskich był Michał Kleofas Ogiński, w owym czasie miecznik WKL, znany kompozytor, a proboszczem pracujący tu od 1764 roku Leon Zatkalik. Wizyta ta wspominała dodatkowo o ławkach i ambonie. Do liturgii używano wielu pięknie oprawionych ksiąg, ewngeliarzy, służebników i innych drukowanych m.in. w Supraślu.
Kolejni właściciele miasta – Kobylińscy wystawili nowy drewniany budynek cerkwi, ponieważ stary spłonął w wielkim pożarze miasta 1809 roku. Sytuacja uległa całkowitej zmianie kiedy w 1875 roku car zlikwidował unię a parafię i cerkiew obrócił na prawosławną co nie odbyło się bez użycia siły i tragedii tutejszej ludności.
Kiedy w 1905 roku car ogłosił edykt tolerancyjny praktycznie wszyscy dawni unici przeszli na wyznanie rzymskokatolickie, co świadczyło o zjednoczeniu obu obrządków jeszcze w czasach unickich. W 1913 roku przeniesiono świątynię na cmentarz przy ulicy Bartoszowej. Kiedy w 1915 roku z terenów tych wycofało się wojsko i duchowieństwo prawosławne, a w 1918 roku Polska uzyskała niepodległość parafie unickie przekształcono na katolickie a cerkwie na kościoły. W 1954 roku cerkiew sokołowska została rozebrana.