История строительства храмов в Муствеэ (русское название Посад Черный) начинается в 30-х годах XIX века, когда два местных жителя Болотов и Красильников отправились во Псков к епископу Нафанаилу (Павловскому) с просьбой открыть в селе православную церковь.
Владыка с большим участием отнесся к просителям, снабдил их необходимой утварью и иконами для иконостаса. Церковь была устроена в доме Болотова.
В 1839 году построена деревянная церковь, освященная в честь иконы Божией Матери «Всех скорбящих Радость». Строительство велось на добровольные пожертвования, собранные первым священником Алексием Орловым.
Храм был возведен на кладбище и существовал до 1948 года, когда его снесли.
На средства казны в 1861-64 гг. по проекту епархиального архитектора А. Эдельсона был построен и освящен в 1866 году каменный храм во имя святителя Николая.
