О точной дате основания прихода в Рыбацкой слободе Переславля-Залесского сведений не сохранилось, но известно, что существовала церковь уже в начале XVII столетия. В патриарших окладных книгах по 1628 году написано: «Церковь Святых Четыредесят Мученик на посаде… дани восемь алтын, четыре деньги, десятильничьих гривна».

В 1652 году при этой церкви была построена другая тёплая церковь и освящена в честь Покрова Пресвятой Богородицы. В писцовых книгах 1653 года в приходе, при этих церквах, записано 82 двора. В переписных книгах 1703 года значится при них священник отец Иоаким Семёнов, в приходе «82 двора, пашни церковной десятина с третью, сена 9 копен».

В 1726–1727 годах обе деревянные церкви – и холодная, и тёплая, оказались ветхи, служить в них стало невозможно и по просьбе священника Иоанна Стефанова с прихожанами, разрешено было устроить новые деревянные церкви, которые в 1728 году были устроены и освящены. Холодная церковь была освящена в то же наименование Святых Севастийских мучеников, а тёплая — в честь Рождества Пресвятой Богородицы.

Вместо этих двух деревянных церквей во второй половине XVIII века, в период подъёма церковного строительства, на средства Московских купцов Максима и Ивана Щелягиных в 1755 году построен каменный храм, ныне существующий. Престолов в нём два: в холодном в честь святых Сорока мучеников Севастийских, а в приделе тёплом — в честь Рождества Пресвятой Богородицы. В приходе церкви состояло тогда около 200 человек.

В 1805 году ко храму святых Сорока мучеников Севастийских был назначен отец Никита Бессонов, бывший ранее преподавателем, а позднее инспектором Переславского духовного училища. В 1824 году он был назначен настоятелем Преображенского собора Переславля и возведён в сан протоиерея.

В 1812 году отец Иоанн Филипповский после окончания богословского отделения Владимирской духовной семинарии стал священником церкви святых Сорока мучеников Севастийских, скончался отец Иоанн 15 апреля 1865 года.

Бывшая при церкви земля, показанная в писцовых книгах, в 1846 году была отобрана в государственное ведомство, в котором состоит Рыбная слобода.

С 1850 года священником в церковь был назначен отец Андрей Сахаров. В 1866 году он был переведен к Смоленской церкви Переславля-Залесского, скончался 14 октября 1889 года.

С 1873 года церковь святых Сорока мучеников Севастийских была приписана к соседней Введенской церкви. Особого причта при храме святых Сорока мучеников не было, богослужение и требы отправлял причт Введенской церкви.

В 1876 году в объединённом из двух храмов приходе служили отец Димитрий Черевский и пономарь Никита Рунов. Приход в то время состоял из «278 душ только мужского пола». В приходе по клировым ведомостям последующих лет: «Числится 205 душ мужского пола и 199 женского; все православные. Церковные документы хранятся в целости: копии с метрических книг с 1803 года, исповедныя росписи с 1809 года. Утварью, ризницей, святыми книгами и богослужебными книгами церковь снабжена достаточно. На каждом из священных сосудов, на потире, сохранилась надпись: «В 1770 году построены сии сосуды в Переславль-Залесский в рыбную слободу к церкви Четыредесят Мучеников в помин души Государева духовника протопресвитера Благовещенского Феофана Феофилактовича…» Сохранились надписи и на некоторых богослужебных книгах, например, на Минее написано: «203 (1695 год). Спасского собора, что у великих государей вверху, диакон Прокопий Феофанов дал сию книгу в Переславль-Залесский в рыбную слободу в церковь Святых Четыредесяти Мучеников по своих родителех во веки неотъемлемо».

В 1895–1907 годах в храме святых Сорока мучеников Севастийских совершал своё служение священномученик Евгений Елховский. Трудами отца Евгения храм во многом преобразился — по его инициативе и замыслу в начале ХХ века началась роспись стен, которые выполнил переславский живописец Василий Петрович Шманаев. Сбор средств производил староста храма Иван Васильевич Дыбцына, особым рачителем и благодетелем храма в годы служения отца Евгения был Василий Иванович Носков.

В 1907–1909 годах в храме служил отец Феодор Делекторский, переведенный из Свято-Николького женского монастыря Переславля-Залесского, впоследствии епископ Орехово-Зуевский Никита.

В 1916 году в храме служил священник Леонид Веселовский. Протоиерей Владимир Елховский, старший сын отца Евгения Елховского в воспоминаниях указал, что в голодном 1918 году «отец Леонид Веселовский ещё по лету уехал от голода куда-то на юг со всей семьей. Был слух, что в пути его семья растерялась, жена умерла». Епископ Переславский, священномученик Дамиан (Воскресенский) на место отца Леонида временно управляющим приходом вновь назначил отца Евгения Елховского.

С конца 1918 года служение в храме начал протоиерей Леонид Гиляревский, переведенный епископом Дамианом из закрытого большевиками Николо-Сольбинского монастыря. Отец Леонид служил в приходе 19 лет, был благочинным отцом Переславля-Залесского.

После революционных событий храм взял в своё ведение приходской совет. Летом 1919 года в церкви случился пожар, и особенно пострадала из-за копоти настенная живопись.

В 1922 году ВЦИК издал указ об изъятии церковных ценностей в пользу голодающих Поволжья. Прибывшую в апреле 1922 года в церковь святых Сорока мучеников Севастийских комиссию по изъятию церковных ценностей встретил отец Леонид (Гиляревский), церковный староста Федосеев и несколько человек верующих. Ознакомившись с описью, комиссия удостоверилась, что в храме имелось только два комплекта богослужебного имущества для двух имеющихся в церкви престолов и ничего лишнего. Тогда комиссия обратила своё внимание на серебряное кадило. Староста и верующие попросили оставить его, так как единственное, кроме этого, имевшееся в церкви медное кадило давно пришло в негодность. Комиссия удовлетворила просьбу верующих. Следующий выбор комиссии пал на Евангелие XVII века в серебряном окладе. Впоследствии это Евангелие всё же не переплавили и не продали за границу лишь благодаря непреклонности директора Переславского музея Михаила Ивановича Смирнова — оно, как и многие другие ценности, осталось в музейной коллекции. Подлинный патриот и знаток своего края, сын священника, этот человек не избежал судьбы многих выступающих в столь сложное время в защиту памятников истории и архитектуры — в январе 1930 года по ложному навету Михаил Иванович был арестован и на 3 года сослан в Туруханский край. Свои научные изыскания он продолжил в Сергиевом Посаде.

После ареста 11 октября 1937 года протоиерея Леонида Гиляревского, несмотря на большой приход из 150 человек, храм святых Сорока мучеников Севастийских был закрыт. Сам отец Леонид, ложно обвинённый за «организацию антисоветской подпольной группировки духовенства», был расстрелян 10 декабря 1937 года в Ярославле,

29 октября 1937 года органы НКВД расстреляли священномученика Евгения Елховского, который также был ложно обвинен в антисоветской деятельности. В августе 2000 года отец Евгений был канонизирован Архиерейским Собором Русской Православной Церкви.

В последующее после 1937 года время советскими властями в храме устраивались библиотека, слесарные мастерские, спасательная станция на озере Плещеево.

В начале 1995 года храм святых Сорока мучеников Севастийских вновь был открыт. В момент возвращения храм внутри был разделен на девять помещений, устроенных для действующей спасательной станции на Плещеевом озере.

Большие труды по открытию монастырей и храмов Переславля-Залесского приложил в те годы архимандрит Анатолий (Аксёнов), через его попечение священнослужителем в церковь был назначен священник Иоанн Герасимов.

7 августа 2010 года архиепископ Ярославский и Ростовский Кирилл (Наконечный) совершил освящение храма.

В 2010 году был устроен иконостас главного придела, где украшения выполнены в виде резьбы по дереву.

В 2013 году силами прихода построена обширная набережная озера и реки, препятствующая размытию берега, и позволяющая всем людям наслаждаться красотой храма в гармонии с природным простором и тихими улицами Переславля-Залесского.

Попечением благодетелей храма Игоря и Ирины Ерохиных летом 2013 года расписаны стены и алтарь в приделе Рождества Пресвятой Богородицы, в феврале 2014 года закончена роспись алтаря главного престола в честь святых Сорока мучеников Севастийских. К осени 2016 года завершена роспись стен и свода главного придела.

В 2021 году проведены работы по замене куполов и крыши, выполнена наружная отделка стен, установлена беседка на территории храма.