Точное время появления Нижнедольского храма не установлено. Однако косвенно о его древности свидетельствуют хранившиеся здесь иконы древнего письма; колокола 1601 г. (по данным клировых ведомостей) и остатки Царских врат времен царя Алексея Михайловича, которые в начале XX в. видел Г.К.Лукомский в кладовой храма при его осмотре.
Пояснение «на Нижнем Долу» восходит к старинному названию местности, где стояла церковь, – Нижний Дол (участок между современным мостом 800-летия и Красным мостом).
В писцовой книге Вологды 1627/28 г. мы находим такие сведения: «Церковь преподоб[наго] Григория, Вологодскаго чудотворца, что на Пельшме, – древяна клецки, а в церкви Божие милосердие образы, книги, и ризы, на колокольнице колокола и всякое церковное строение приходных людей. М[есто] церковное, что была церковь Рождества Пречистые Богородицы, а земли под церковью и около церкви и места церковнаго в длину 20 с[ажен], попер[ег] тож, а у церкви служит поп Карп Фомин» (см. список с писцовой книги города Вологды, сделанный в 1629 г., с.122). Очевидно, что речь идет о теплом и холодном храмах одного прихода, из которых один к этому времени по неустановленным причинам уже не существовал. В окладной книге 1691 г. мы вновь обнаруживаем сведения о церкви Рождества Богородицы на Нижнем Долу. Судя по размерам выплачиваемой церковной дани, благосостояние храма в это время было вполне удовлетворительным (Суворов, с.601). Его приход был не из самых бедных: еще в начале XVII в. около храма стояли не только дворы посадских людей, но и несколько дворов крупных торговцев («гостей»), в том числе московских, а по переписной книге Вологды 1711–1712 гг. на Нижнедольском берегу располагался ряд кожевенных заводов.
По данным историка-краеведа Н.И.Суворова, каменное здание церкви было выстроено в 1779 г. после пожара 1773 г., в котором погибло деревянное здание (Суворов, с.646). В учетно-охранной документации этот памятник архитектуры ошибочно датирован концом XIX в.
В связи с тем, что в XIX в. количество прихожан стало сокращаться, в 1864 г. к Богородицкой церкви были причислены воинские чины пехотного резервного батальона, расквартированного в Вологде (Разные известия...,с.72). К началу XX в. в церкви Богородицы на Нижнем Долу было три престола: в холодном храме – главный престол в честь Рождества Пресвятой Богородицы, в левом приделе теплого храма – престол во имя Григория Пельшемского, в правом – во имя Николая Чудотворца.
Храм Рождества Пресвятой Богородицы на Нижнем Долу был закрыт в марте 1930 г. Здание лишили крестов и глав, но не разрушили, как планировалось, а использовали под хозяйственные нужды различных предприятий. К нему были сделаны пристройки, помещения разгорожены, некоторые окна превращены в двери. В июне 2014 г. состоялось учредительное собрание, принявшее решение о создании Богородицкого прихода и было положено начало возрождению храма. Церковь дала название Пречистенской набережной реки Вологды.
Ныне при храме действует МПРО ПХ Рождества Пресвятой Богородицы на Нижнем Долу г.Вологды Вологодской епархии РПЦ МП. Молебен совершается по субботам в 11-00.