Начальный период истории этой церкви по традиции связывается со сретением (встречей) вологжанами на окраине города местной святыни – почитающейся чудотворной иконы Димитрия Прилуцкого. Что касается датировки этого события, то здесь существуют две версии. По наиболее распространенной – оно произошло в 1503 г. и соотносится с тем, что икону по особому откровению брал с собой в поход на Казань Иван III, а затем возвратил ее (или ее список) обратно в Спасо-Прилуцкий монастырь. По другой – икону возвратил в Вологду в 1580 году Иван IV, и это было связано с ее «участием» при походе на Казань в 1552 г. По мнению Н.К.Голейзовского, проанализировавшего различные сообщения, связанные с этой иконой, первая дата могла появиться из-за ошибки «писца, перепутавшего, как это нередко случалось, похожие буквы цифири». Он не исключал, «что именно тогда начались споры о том, оригинал или копия были возвращены в монастырь, послужившие поводом для возникновения в конце XVI века двух взаимоисключающих вариантов легенды». С упоминавшейся иконой связано и изначальное посвящение церкви Димитрию Прилуцкому, о чём свидетельствует писцовая книга Вологды 1627/28 г.: «Церковь преподобнаго Димитрия, Прилуцкаго чудотворца, другая церковь преподобнаго Кирила, Белоезерского чудотворца, – обе древяны клетцки, а в церквах Божие милосердие образы и книги, и ризы и на колокольнице колокола и всякое церковное строенье приходных людей, а под церквами и около церквей земли в дл[ину] 62 саж[ени], попер[ег] 25 с[ажен], у церквей служит поп Филипп» (см. список с писцовой книги города Вологды, сделанный в 1629 г., с.134). Поскольку в Вологде были две церкви с подобным посвящением, то часто уточнялось – церковь Димитрия Прилуцкого «в Кобылкине улице».
В хранящемся в фондах ВГИАХМЗ списке церквей Вологды, который датирован 1 сентября 1760 г., впервые удалось обнаружить сведения о дате постройки существующего ныне каменного храма: «Церковь каменная святых и равноапостольных царей Константина и Елены с приделами иже во святых отца нашего Филиппа, митрополита Московскаго и всея России, чудотворца, внизу теплая преподобнаго отца нашего Димитрия, Прилуцкого чудотворца, с приделом преподобнаго Кирилла, Белоезерского чудотворца, зачата строить наместо деревянной в 1657-м, а окончена и освящена в 1664-м годех» (ВГИАХМЗ. Ф.2. Оп.1. Д.73. Л.120об.). В новой каменной церкви появился престол во имя святых равноапостольных царей Константина и Елены, и в окладной книге 1691 г. она уже именуется «Димитрия Прилуцкого и Царя Константина в Кобылкине улице» (Суворов, №15, с.601). Престол во имя святителя Филиппа, митрополита Московского и всея России, был упразднен после ремонта в 1850-х годах. В начале ХХ века церковь имела три престола: в верхнем храме – во имя святых равноапостольных царей Константина и Елены, в нижнем храме на северной стороне – во имя семи отроков Эфесских, на южной – во имя преподобного Димитрия Прилуцкого.
Священником в Цареконстантиновской церкви в 1898–1911 гг. служил отец Сергей Арсентьевич Непеин (1870–1911). Происходил он из старинного вологодского рода Непеиных, одним из представителей которого считается Осип Непея – первый русский посол в Англии в середине XVI века. Непеин был помощником заведующего Вологодским епархиальным древлехранилищем, членом Постоянной церковно-археологической комиссии любителей истории и древностей – первого общественного объединения историков-краеведов Вологды. Как было сказано в некрологе, «это был единственный в городе, а может быть и во всей епархии по своей разносторонней деятельности священник, умевший среди пастырских трудов находить время и для научных занятий». Он много занимался фотографией, снимая памятники истории и культуры. С.А.Непеин написал одну из первых общих популярных работ по истории города – «Вологда прежде и теперь», в которой, в частности, описал издревле установившееся в Вологде празднество в память сретения в XVI в. чудотворной иконы Димитрия Прилуцкого: «После ранней литургии 3 июня здесь и в каф[едральном] соборе начинается благовест в перебор. К Цареконстантиновскому храму приходят с хоругвями и святыми иконами от ближайших храмов, и общий крестный ход направляется в собор, соединяясь по пути с другими крестными ходами. Отсюда, уже с участием преосвященного владыки, крестный ход направляется … за город к Прилуцкому монастырю. Стройное шествие при участии городского общества хоругвеносцев в красивых костюмах, со множеством хоругвей, сопровождаемое толпами народа, очень красиво со стороны».
24 февраля 1930 г. Цареконстантиновская церковь была закрыта. В здании, охранявшемся с 1920-х гг. как памятник истории и культуры, в разное время размещались учреждения культуры и трикотажная фабрика. Позднее здание несколько раз реставрировалось. В 1997 г. храм возвращен верующим. В 2001 г. возрождена традиция крестных ходов в память сретения иконы Димитрия Прилуцкого. 10 апреля 2008 г. на колокольню были подняты восемь новых колоколов весом от 10 до 430 кг, отлитых в городе Тутаеве.
Ныне при храме действует МПРО ПХ святых равноапостольных царей Константина и Елены г. Вологды Вологодской Епархии РПЦ МП, имеется воскресная школа. Контактный телефон: 72-84-84.
Литургия совершается в субботние, воскресные, праздничные дни с 9:00 часов. Накануне воскресных и праздничных дней – Всенощное бдение, начало в 17:00 часов. Храм открыт ежедневно с 8:00 до 18:00 часов. С 9:00 до 12:00 совершаются требы: молебны, панихиды, отпевания, крещение.
Среди чтимых святынь - икона с частицей мощей св.Луки Крымского, икона с частицей мощей муч.Татианы.