После убийства в 1881 году императора Александра II в Мелекессе был объявлен сбор пожертвований на строительство храма в память мученической смерти Царя-Освободителя. В силу масштабности предприятия и ряда трудностей в разработке проекта место под постройку храма было отведено только в 1890 г., в июле состоялась закладка. Проект составил самарский епархиальный архитектор Т.С. Хилинский.
Строили храм надежно и со знанием дела. Для прочности сооружения в растворе при кладке кирпичей использовали куриные яйца, которые везли возами со всех окрестных деревень. Кресты поднимали в июне 1893 года при большом стечении народа. Отметим, что позолоченный крест главного купола имел высоту более 5 метров. Летом 1894 года строительство было закончено, храм торжественно освятили в честь святого Александра Невского. Собор получился на редкость красивым; возведен он был из красного кирпича, а потому в народе его прозвали "Красной церковью".
Ступенчатые стены под крестовым сводом были выложены с большим разнообразием архитектурных и декоративных элементов. На своде покоились основания пяти прямоугольных барабанов, увенчанных каждый восьмигранными шатрами и позолоченными куполами над ними (взгляните еще раз на фотографию, это действительно очень редкий прием). В заде для прихожан было много колонн, естественный свет проникал слабо (к тому же, в большим круглых окнах-розах были установлены темные витражи), и храм был освящен большим количеством настенных и висячих светильников.Огромная люстра с тысячами огней была подвешена на главном куполе и могла подниматься и опускаться при помощи лебедки".
В 1907 г. к собору был пристроен обширный притвор с пятидесятиметровой трехъярусной колокольней под восьмигранным шатровым завершением. Её строительство контролировал В.П. Шаманским, занявшим пост самарского епархиального архитектора после смерти Хилинского в 1905 г., но проект колокольни близко повторяет колокольню Казанской церкви в Верхнем Санчелееве, которую Хилинский построить успел (таким образом, весь мелекесский собор, пусть и построенный в два этапа, можно уверенно называть творением Хилинского). Собор Александра Невского был закрыт последним из храмов Мелекесса, в 1939 году, после чего в нем размещался комсомольский клуб, другие организации и общежития. В 1954 году было постановлено разобрать собор на строительные материалы, и к 1956 году он был полностью уничтожен. Сегодня на месте собора расположен закрытый кинотеатр "Мир". На близлежащей площади Советов в 2007 году была достроена новая церковь Спаса Преображения, выполненная по мотивам утраченного собора.