На левом берегу реки Трубеж, в самом её устье возвышается каменный храм в честь Сорока мучеников с пределом Рождества Богородицы. Церковь существовала в начале XVII века. В патриарших окладных книгах 1626 года написано, «Церковь Святых Четыредесят Мученик на посаде… дани восемь алтын, четыре деньги, десятильничтих гривна».
В 1652 году при этой церкви была построена другая тёплая церковь и освящена в честь Покрова Пресвятой Богородицы. В писцовых книгах 1653 года в приходе, при этих церквах, записано 82 двора, а в переписных книгах 1703 года значится при них священник Иоаким Семенов, в приходе 82 двора, пашни церковной десятина с третью, сена 9 копен.
В 1726-1727 годах обе церкви и холодная и тёплая, оказались ветхи, служить в них стало невозможно и, по просьбе священника Ивана Стефанова с прихожанами, разрешено было устроить новые деревянные же церкви, которые в 1728 году были устроены и освящены. Холодная церковь была освящена в то же наименование, а тёплая в честь Рождества Пресвятой Богородицы.
Вместо этих двух деревянных церквей в 1755 году, на средства Московских купцов Максима и Ивана Щелягиных построен каменный храм, ныне существующий. Престолов в нём два, в холодной в честь Сорока мучеников, а в приделе тёплом в честь Рождества Пресвятой Богородицы. Утварью, ризницей, святыми книгами и богослужебными книгами церковь снабжена достаточно. На каждом из священных сосудов, на потире, сохранилась надпись, «В 1770 году построены сии сосуды в Переславль-Залесский в рыбную слободу к церкви Четыредесят Мучеников в помин души Государева духовника протопресвитера Благовещенского Феофана Феофилактовича…»
Сохранились надписи и на некоторых богослужебных книгах, например, на Минее написано, «Спасского собора, что у великих государей вверху, диакон Прокопий Феофанов дал сию книгу в Переславль-Залесский в рыбную слободу в церковь Святых Четыредесяти Мучеников по своих родителех во веки неотъемлемо». Подобная же надпись эта 1734 года есть и на Служебнике. Церковные документы хранятся в целости, копии с метрических книг с 1803 года, исповедныя росписи с 1809 года. Особого причта при этой церкви нет, богослужение и требы отправляет причт Введенской церкви, к которой данная церковь приписана с 1873 года. В приходе по клировым ведомостям числится 205 душ мужского пола и 199 женского, все православные. Бывшая при церкви земля, показанная в писцовых книгах, в 1846 году отобрана в ведомство, в котором состоит Рыбная слобода. В 1805 году ко храму Сорока мучеников был рукоположен учитель, а позднее инспектор Переславского Духовного училища Никита Ильич Безсонов. В 1824 году он был назначен настоятелем Преображенского собора и возведен в сан протоиерея. Иван Козьмич Филипповский после окончания богословского отделения Владимирской духовной семинарии в 1812 году, священник Четыредесятской, Сорока мучеников, церкви города Переславля, скончался 15 апреля 1865 года. С 1850 года священником Четыредесятской церкви Переславля был назначен Андрей Иванович Сахаров. В 1866 году он был переведен к Смоленской церкви Переславля. Скончался 14 октября 1889 года.
С 1873 года церковь Сорока мучеников города Переславля была приписана к соседней Введенской Церкви. Особого причта при храме Сорока мучеников не было, богослужение и требы отправлял причт Введенской церкви. В 1876 году в объединенном из двух храмов приходе служили священник Димитрий Черевский и пономарь Никита Рунов. Приход Введенской и Четыредесятской церквей в то время состоял из 278 душ только мужского пола. В 1880-х годах приход церкви Сорока мучеников снова обрел самостоятельность. С 1895 года по 1907 год в храме Сорока мучеников Севастийских совершал своё служение Евгений Елховский. Трудами Священномученика в храме появились настенные росписи, храм во многом преобразился. Мученическая кончина за Христа протоиерея Евгения Елховского последовала 29 октября 1937 года. В 1916 году в храме служил священник Леонид Веселовский. Владимир Евгеньевич Елховский вспоминал, что в голодном 1918 году «отец Леонид Веселовскии ещё по лету уехал от голода куда-то на юг со всей семьёй. Был слух, что в пути его семья растерялась, жена умерла». На его место временно управляющим приходом епископ Дамиан назначил о. Евгения Елховского.
В 30-х годах, несмотря на большой приход, 150 человек, храм был закрыт. Последнего священника протоиерея Леонида Гиляревского расстреляли. В последствии в храме располагались библиотека, слесарные мастерские, а в последнее время спасательная станция.
В 1995 году по благословению архиепископа Ярославского и Ростовского Михея храм Сорока мучеников Севастийских вновь был открыт, в храме возобновились богослужения.