На месте разрушенной турецкой мечети Биюк-Джами в 1808 г. с высочайшего повеления царя Александра I городские власти решили возвести православный соборный храм во имя Александра Невского. Было выделено 47 тыс. рублей, и в 1810 г. приступили к работам. Но начались первые неудачи: не хватило денег, умер подрядчик. Собор по-прежнему оставался в греческой Николаевской церкви. В 1847 г. казна снова отпустила деньги, была объявлена добровольная подписка на пожертвования, денег снова не хватило. Вмешалось губернское правление и предписало выделить необходимую сумму. Наконец, в 1871 г. приступили к строительству, и в 1873 г. собор был построен и торжественно освящен епископом Гурием.

Новый собор имел два боковых придела: во имя святого Николая Мирликийского и святого Гурия и в честь преподобной Феодосии. Собор построен в византийском стиле, внутри украшен росписями, иконами и мраморными колоннами из древнего византийского храма. При раскопках была найдена каменная плита с изображением святого Николая, которую поместили в алтаре собора. В Александро-Невском соборе находилась и древняя Богородицкая икона на полотне работы итальянского мастера-живописца XVI в. Святыней собора была и древняя русская икона Знамения Пресвятой Богородицы (чудотворная). Ее подарил собору в 1876 г. московский купец Рукавишников. И.К.Айвазовский написал для собора колоссальных размеров полотно «Хождение Христа по водам», икону «Спасение утопающего Апостола Петра». В соборе в 1875 г. был похоронен вице-адмирал В.М.Микрюков, участник морского сражения под началом Нахимова при Синопе, герой обороны Севастополя в Крымскую войну 1854-56 гг. Руководил взрывом пороховых складов при отходе на Северную сторону. Командир линейного корабля «Чесма» Микрюков в последние годы своей жизни прожинал в Феодосии. При соборе была открыта женская соборная школа. Во время русско-турецкой войны 1 января 1877 г. город обстреляли турецкие корабли, но ни один снаряд не задел собор. В октябре 1914 г. город снова подвергся обстрелу военных кораблей, три снаряда повредили купол собора. Пострадали также Введенская и Екатерининская церкви.

В годы советской власти собор закрыли, а в 1933 году Александро-Невский собор, один из красивейших христианских храмов в Крыму, был варварски снесен. Место захоронения адмирала В.М.Микрюкова утрачено.