Среди событий 1793 года летописец Вельского Троицкого собора упоминает следующе: «По благословению преосвященнаго Иринея, епископа Вологодскаго и Устюжскаго, на кладбище деревянная святая церковь во имя Успения Пречистыя Богородицы с двумя приделами Николая Чудотворца и преподобных Симеона Столпника и Кирилла Белоезерскаго заложена по церковному чиноположению протопопом Стефаном Левицким с братией мая 15-го числа, и начата с Божией помощию строить, и по выстройке того ж лета на оной церкви животворящий деревянный крест с церковною церемонией поставлен сентября 25-го числа».
В следующем году для кладбищенской церкви были куплены в Москве: «4 колокола, из которых большой 11 пудов 20 фунтов, а прочие в подборе; цена каждому пуду 17 рублей». В 1795-ом в летописи говорится, что «на кладбище в приделе на правой стране 1-й храм во имя Николая Чудотворца вельским протопопом Стефаном Левицким с тринадцатью священниками и одним диаконом сентября 1-го числа освящен торжественно». А через год освящён ещё один придел преподобных Симеона Столпника и Кирилла Белоезерскаг. В 1797-ом для Успенского храма был «куплен в Ростове колокол в 21 пуд 30 фунтов на деньги вельскаго купца Алексия Честикова по 18 рублей за пуд». Торжественное освящение главного престола нового кладбищенского храма состоялось в 1803 году вельским протопопом Стефаном Левитским.
В архитектурной основе церкви лежит восьмерик на четверике, завершенный восьмигранной пучиной с одной главой. К нему примыкают пятистенный алтарь и широкая трапезная. Главки на постаментах, возвышавшихся над крышей трапезной и над покрытием алтаря, существенно обогащают архитектурное решение церкви, придавая ей городской облик. С западной стороны вплотную была поставлена высокая колокольня, завершавшаяся куполом со шпилем. До настоящего времени она не сохранилась.
Ремонт, вероятно, не первый, проводился в 1910 г. Памятник уже в наше время был в очередной раз поновлен. Сейчас здание имеет новую кровлю и обшивку стен, но в общих чертах сохраняет свои исторические формы и используется по своему назначению.