Вблизи крепости Еникале в XVIII в. была построена церковь в честь Успения Пресвятой Богородицы и второй придел Святителя Николая, которая принадлежала греческой епархии. Послевоенные годы церковь не была полностью разрушена. Основные строения уцелели, где и проводились богослужения. В коммунистические годы церковь была закрыта, и богослужения в ней не проводились. В бывшем храме располагалась лечебная клиника. Через некоторое время клиника была закрыта и перестроена для жилья людей. Со временем проживающих людей переселили в квартиры, а само строение было полностью разрушено. В 2001 году на основании бывшего Свято-Успенского храма и придела в честь Святителя Николая возникла мысль создать Свято-Николаевскую церковь в центре поселка Стройгородок по улице Ярошенко, 14 а, где и был освящен земельный участок, на котором восстановлен крест.
С 2002 года совершались Богослужения в металлическом контейнере, который был завезен на освященный земельный участок, вблизи которого располагался овощной ларек, принадлежавший рынку. По ходатайству священника Владимира Фастовича этот ларек был передан для перестройки церковного помещения (2003 г.). Постепенно проводилась перестройка под церковь Святителя Николая. Земля, на которой совершалось строение, была оформлена документом договора-аренды.
В 2004 году Архиерейским Синодом Русской Православной Церкви за границей во главе с Митрополитом Лавром было вынесено решение оказывать финансовую помощь строительству храма, средства перечислялись на церковный счет. На преобретенные деньги продолжалось строительство храма, который был зарегистрирован в Совете по делам религий и относился к Одесской Епархии. По 2007 год регулярно совершались Богослужения.
С 2008 года по благословению священника Владимира Фастовича Свято-Николаевский приход перешел в Симферопольскую и Крымскую Епархию. 17 декабря 2008 года Митрополитом Лазарем был выдан указ под №59 о назначении протоиерея Владимира Фастовича к Свято-Николаевскому храму города Керчи. 16 ноября 2008 года был выдан церковный устав, зарегистрированный в Совете по делам религий.
По материалам официального сайта Феодосийской епархии
