После постройки Нового моста в 1874 году, соединившего Старый город с восточной стороной каньона, активно начался застраиваться район, названный Новым планом. Градостроительной доминантой застройки центральной части Нового плана стала церковь Св. Александра Невского, возведённая на большой Торговой площади, откуда открывался живописный вид на Старый город. Храм был построен в память 100-летия воссоединения Подолья с Россией.
Закладка церкви была совершена 2 мая 1891 года Преосвященным Димитрием, Епископом Подольским и Брацлавским, при участии Преосвященного Акакия, Епископа Балтского, и множества духовенства, в том числе почти всех благочинных Подольской епархии, съезд которых проходил в эти дни в городе. К месту закладки храма был совершён крестный ход.
Храм строился на пожертвования, собранные Св. Александро-Невским попечительством, учреждённом в августе 1875 года. По смете стоимость составила 72 208 рублей 42 копейки. По сведениям Е. Сецинского, в 1893 году было уже окончена кладка стен и возведён главный купол и в этом же году храм предполагалось открыть. Но в связи с задержками в отделке и оформлении храм был освящён и открыт лишь 24 ноября 1897 года.
Это был пирамидального силуэта пятиглавый храм поздневизантийского стиля, соединённый крытым переходом с низкой звонницей. Основной объём храма - крестообразный в плане с большим центральным куполом на барабане диаметром около 12 метров, четырьмя массивными трёхчетвертными куполами на барабанах по сторонам креста и четырьмя наружными одноярусными приделами.
Конструктивно слаженный переход от прямоугольных сторон креста до круглых барабанов боковых куполов и от центрального подкупольного квадрата до барабана купола был решён сталактитовыми тромпами, вынесенными на фасад, что чрезвычайно обогатило архитектурный вид сооружения. Пирамидальная объёмно-пространственная структура храма высотой около 40 метров с апсидой в форме трёхчетвертной поздневизантийской купольной ротонды создавала величественное впечатление. Тяжёлую массу строения компенсировали прозрачные аркады купольных бань и мелкая пластика декора.
Проект храма был разработан губернским архитектором Моисеем Баллогом и инженером Иваном Калашниковым на основе высочайше утверждённых проектов. По аналогичному проекту была заложена в 1889 году, построена и в октябре 1898 года освящена церковь Милующей Божией Матери в Санкт-Петербурге (архитектор В.А. Косяков, инженер Д.К. Пруссак).
Главный престол каменецкого храма был посвящён Св. Александру Невскому, тезоименитого покровителя императора Александра III, в царствование которого исполнилось 100-летие воссоединения Подолья с Россией. Один из приделов был посвящён имени св. великомученице Екатерине, тезоименитой императрице Екатерине II, в царствование которой произошло воссоединение. Ещё один придел был посвящён св. Николаю. Помещения церкви обогревалось паровым отоплением.
Храм имел двухъярусный иконостас работы московского мастера Охапкина. В числе пожертвований на храм был крест, присланный в подарок императрицей Александрой Федоровной (супругой Николая II). При церкви в начале ХХ века действовало Св. Александро-Невское братство с народной читальней и библиотекой.
По справочникам Подольской губернии известны фамилии некоторых настоятелей Александро-Невской церкви. В 1900 году настоятелем был священник Виктор Георгиевич Чекан, второй священник храма - Никанор Донатович Крестианполь. В 1909 году настоятелем церкви был Николай Афанасьевич Курчинский, второй священник храма - Ананий Разумовский. В 1911 и 1913 годах настоятелем церкви был тот же Николай Афанасьевич Курчинский.
В 1936 году храм по решению советских властей был снесён, на его месте был устроен сквер с фонтаном. 7 ноября 1947 года, в день 30-летия Октябрьской революции в сквере был установлен памятник В.И. Ленину и И.В. Сталину. Сквер назвали именем Григория Котовского, как и улицу проходящую вдоль сквера (б. Соборную). В новогодние праздники здесь устанавливалась ёлка и проходили народные гуляния.
12 марта 1998 года был заложен и освящён первый камень в фундамент и начался сбор пожертвований на восстановление храма. 12 сентября 2011 года в присутствии многочисленных верующих заново отстроенный в статусе кафедрального собора храм Св. Александра Невского был освящен архиепископом Каменец-Подольским Федотом Украинской православной церкви Московского патриархата.
О. Пламеницька, "Сакральна архітектура Кам'янця на Поділлі", 2005 г.; Е. Сецинский, "Исторические сведения о приходах и церквах Подольской епархии", 1895 г.; Е. Сецинский, "Город Каменец-Подольский", 1895 г.; В.К. Гульдман, "Подольский адрес-календарь", 1900 г.; Г.С. Станкевич, "Подольский адрес-календарь", 1909 г.; В.В. Филимонов, "Памятная книжка Подольской губернии на 1911 год"; Справочник "Весь юго-западный край", 1913 г.; О. Будзей, "Соборна", "Подолянин", 2004 г.
