Pierwsza cerkiew unicka w Starym Pawłowie została wzniesiona prawdopodobnie XVI w., następnie w tym miejscu została wybudowana drewniana w 1741 r., która to spłonęła w pożarze, a w jej miejsce około 1793 r. została odbudowana mała świątynia pod wezwaniem Wniebowzięcia NMP, która to w 1875 r. została przejęta przez Rosjan i przemianowana na cerkiew prawosławną.
Cerkiew zasłynęła z cudownej ikony św. Mikołaja, która mimo przeciwności losu cudownie ocalała. W czasie pierwszej wojny światowej cerkiew popadła w ruinę, przez to ikona była narażona na niekorzystne warunki atmosferyczne, następnie nietknięta ocalała z pożaru. Po odzyskaniu przez Polskę niepodległości powróciła do unitów.
W dniu 28 lipca 1925 roku dekretem biskupa Henryka Przeździeckiego erygowano parafię obrządku wschodniosłowiańskiego przy kościele św. Jana Ewangelisty we wsi Bubel Stary, ale ze względu na trudności zewnętrzne świątynia w Bublu nie mogła być używana dla celów parafii. Do tego celu służyła kaplica pod wezwaniem św. Mikołaja Cudotwórcy w Pawłowie Starym.
Została wzniesiona w latach 1929-30 w miejsce starej i zniszczonej. Świątynia została wybudowana jako cerkiew orientowana, drewniana o konstrukcji zrębowej; została oszalowana i z więźbą dachową krokwiowo-jętkową. Nawa została wzniesiona na planie kwadratu, gdzie prezbiterium było węższe, zamknięte trójbocznie, a do niego przylegała od południa prostokątna zakrystia. Nad prostokątnym babińcem znajdowała się dwukondygnacyjna, ośmioboczna wieża, która została zwieńczona ostrosłupowym hełmem. W cerkwi znalazła swój dom ocalała ikona św. Mikołaja. Przed jej wizerunkiem modliło się wielu wiernych, szczególnie 19 grudnia, w dniu odpustu.
W 1946 roku została poświęcona jako kaplica rzymskokatolicka pw. Św. Mikołaja. W 2011 r. została gruntownie wyremontowana.