Время постройки храма неизвестно. Однако возведена она была на фундаменте старинной греческой церкви и, по достоверным сведениям, именовалась во имя Св. Николая Чудотворца. Размеры ее были довольно велики для того времени: высота -7,3 м, ширина-14,2 м, а длина-15 м. Церковь вмещала до 600 молящих. После присоединению Крыма к России службы в церкви продолжались еще несколько лет, но затем были прекращены — по недостатку духовенства, сама церковь была превращена в склад казенного фуража и провианта.
С 1811 г. было принято решение о возобновлении богослужений в храме. Храм был освящен как соборный храм Феодосии. Градоначальник Феодосии Семен Броневский на свои средства пристроил к нему с трех сторон притворы с навесами, а над притвором с западной стороны - деревянную колокольню. В 1820 году ремонтом и реконструкцией церкви руководил Таврический архитектор Леммерман Мейстер Иоганн. Еще раз храм перестроили в 1850 году: под руководством архитектора Никифора Черкунова деревянная колокольня была разобрана и вместо нее выстроена каменная. В 1861 году, во время своего визита в Феодосию, собор посетил император Александр II.
В 1873 году церковь была передана полку и стала именоваться «военной», ее освятили во имя Святителя Николая Чудотворца, архиепископа Мирликийского. На средства полка Николаевская церковь была обновлена и на стенах в 1888 году были размещены доски с именами павших в боях Виленцев. Осенью 1914 года в связи с убытием полка на фронт Николаевская церковь была передана 35-му запасному пехотному полку, размещенному в Виленских казармах. В 1924 году церковь была разрушена.
http://kafanews.com/novosti/106007/vilenskie-kazarmy-i-voennaya-tserkov-sv-nikolaya_2015-07-11
Известный ученый-крымовед Мурзакевич, описывая древние храмы Таврической епархии в хронологии храмов за 1791 год, отмечает Феодосийскую церковь во имя святителя Николая в числе древнейших.
В 1791 году церковь стала собором. Затем феодосийский градоначальник С.М. Броневский пристроил к церкви притворы с навесами и над притворами с западной стороны деревянную колокольню. Когда в 1873 году был построен новый городской Александро-Невский собор, Никольская церковь стала называться "военной", так как в ней проводились богослужения для нижних чинов и офицеров расположенных поблизости воинских частей, в частности, Виленского полка. В 1876 году императрица Мария Александровна даровала церкви ценный складень святителя Николая Чудотворца в серебре. На средства полка Николаевская церковь была обновлена и по стенам в 1888 году были размещены мраморные доски с именами павших в боях виленцев. Впоследствии к ней было приписано еще два храма: Вознесенская церковь на военном кладбище и Алексеевская церковь в лагере.
Осенью 1914 года, в связи с отбытием Виленского полка на фронт, Николаевская церковь была передана 35-му запасному батальону (с 1915 года - полку), размещенному в виленских казармах.
В 1924 году эта древняя церковь была разрушена.
В мае 2011 года на последней сессии Феодосийского городского совета депутаты выделили управлению Симферопольской епархии земельный участок, где ранее стоял храм, в целях восстановления церкви.
https://drevo-info.ru/articles/17627.html
2 мая 2016