Cреди исчезнувших храмов Феодосии числится Александро-Невский собор, возведенный в XIX веке на месте нынешнего Морского сада. До захвата Крыма турками здесь находилась древняя христианская церковь. Турки превратили ее в главную мечеть города, дав название Султан-Керим. Но когда в 1870 году начали подготовку к строительству собора, то при разрытии фундамента мечети нашли древнее изображение святителя Николая на каменной плите.
Cобор во имя святого Александра Невского был построен в виде трехнефной базилики. В плане здание представляло собой крест. Свет попадал в храм через большие окна в северной и южной стенах боковых нефов. В центральной части собора круглые окна сочетались с прямоугольными углублениями, в которых были высечены кресты. Собор венчал купол, он покоился на световом барабане с арочными нишами, в которых были устроены круглые окна. Между нишами находились колонны. Г. Москвич в своем путеводителе так описывает внутреннее убранство храма: "В соборе обращает на себя внимание образ Спасителя, идущего по водам, кисти И.К.Айвазовского, и изображение святого Николая, епископа Мирликийского с евангелием, найденное в фундаменте мечети при постройке храма". Территория вокруг собора была обнесена оградой.
Aлександро-Невский собор стал украшением города и центром его общественной жизни. Ни одно важное событие в городе не начиналось без богослужения в главном храме. Здесь хранилась икона Божией Матери "Знамение", считавшаяся покровительницей Феодосии.
Эта икона Пресвятой Богородицы прославилась в Новгороде. В 1170 году город осадили войска соединенных сил русских удельных князей. У новгородцев было мало сил, всю свою надежду они возложили на Господа. Святитель Иоанн Новгородский три дня молился перед иконой Спасителя и вдруг услышал голос: "Иди в церковь Господа Иисуса Христа на Ильиной улице, возьми образ Пресвятой Богородицы и поставь на городскую стену". Утром диакон и клирики пришли в храм, но, как ни старались, не могли подвинуть икону. Тогда сам Иоанн пришел в храм, пал перед иконой на колени и со слезами просил о помощи. И вот, когда все люди запели: "Представительство христиан непостыдное, ходатайство ко Творцу непреложное, не призри грешных молений гласы...", икона внезапно подвиглась сама собою. Иоанн принял ее на руки, поцеловал и вознес на городскую стену.
Вдруг одна из стрел нападающих попала в лик Богоматери. Тотчас икона поворотилась ликом к городу, и из глаз Богородицы брызнули слезы. В тот же миг ужас объял нападающих, они стали побивать друг друга, и были разбиты новгородцами. В память об этом был установлен праздник в честь иконы "Знамение", совершаемый 10 декабря.
Список с этой знаменитой иконы бережно сохранялся и передавался из поколения в поколение в роду полковника Николая Хрущева, который в XIX веке владел селом Насыпкой, ныне Насыпное. В 1863 году зима выдалась особенно холодной, от сильных морозов в Насыпкое начался падеж скота, что для многих крестьянских семей означало гибель. Тогда крестьяне, получив разрешение хозяина, взяли икону Знамения, обошли с нею село, поставили в церкви и отслужили перед ней молебен. Божья Матерь, вняв их молитвам, помогла, и падеж скота прекратился.
Узнав об этом чуде, епархиальное начальство обратилось к Хрущеву с предложением поместить эту икону навсегда в насыпкойской церкви, чтобы верующие могли свободно молиться перед ней, Но Хрущев, обладавший неуживчивым, вздорным характером, отказался наотрез. Из-за семейных неурядиц он должен был в короткий срок покинуть Насыпкой, имение своей супруги, и переехать в Феодосию, Неоднократно к нему обращались духовные лица, в том числе сам епископ Алексий, с просьбой поставить икону в одном из феодосийских храмов, и вновь получили отказ, Николай Хрущев объяснял просителям, что икона для него священна, хотя точно не знал ее истории. Икона являлась списком с чудотворного образа Знамения Божией Матери, но кем и когда написана, неизвестно. Как она попала к боярам Хрущевым, также оставалось загадкой, но в роду передавались от отца к сыну сказания о чудесах, творимых ею. Очевидно, икона была написана для храма, так как имела большие размеры - для ее перенесения в Феодосию понадобилось пять человек.
После смерти полковника Хрущева икона перешла к жене московского потомственного почетного гражданина Елене Кузьминичне Рукавишниковой. Она украсила святыню новой сребропозолоченной ризой с драгоценными камнями и 9 августа 1876 года передала ее феодосийскому собору Александра Невского. Икона стала главной святыней собора. Ее установили у северной стены храма в правом приделе.
В 1877 году Турция объявила войну России. Многие храмы приморских городов, боясь разграбления, увозили свои святыни в Симферополь, но феодосийцы обратились к архиепископу Симферопольскому и Таврическому Гурию с мольбами оставить икону Знамения Божией Матери в соборе. Они верили, что Заступница спасет и убережет их и Во время Первой мировой войны, в октябре 1914 года, Феодосия вновь пострадала от бомб и снарядов. В куполе Александро-Невского собора три снаряда пробили дыру, но сам храм остался цел. Погиб он в советское время. В апреле 1922 года из храма вывезли более двух пудов золотых и серебряных предметов: риз, крестов, лампад и другой церковной утвари, Конечно же, сняли богато украшенную ризу и с чудотворной иконы, В 1932 году собор закрыли, а спустя год - снесли. До сих пор неизвестно, где находится икона Знамения Пресвятой Богородицы - покровительница Феодосии.