После убийства в 1881 году императора Александра II в Мелекессе был объявлен сбор пожертвований на строительство храма в память мученической смерти Царя-Освободителя. В силу масштабности предприятия и ряда трудностей в разработке проекта место под постройку храма было отведено только в 1890 г., в июле состоялась закладка. Проект составил самарский епархиальный архитектор Т.С. Хилинский. 

Строили храм надежно и со знанием дела. Для прочности сооружения в растворе при кладке кирпичей использовали куриные яйца, которые везли возами со всех окрестных деревень. Кресты поднимали в июне 1893 года при большом стечении народа. Отметим, что позолоченный крест главного купола имел высоту более 5 метров. Летом 1894 года строительство было закончено, храм торжественно освятили в честь святого Александра Невского. Собор получился на редкость красивым; возведен он был из красного кирпича, а потому в народе его прозвали "Красной церковью".

Ступенчатые стены под крестовым сводом были выложены с большим разнообразием архитектурных и декоративных элементов. На своде покоились основания пяти прямоугольных барабанов, увенчанных каждый восьмигранными шатрами и позолоченными куполами над ними (взгляните еще раз на фотографию, это действительно очень редкий прием). В заде для прихожан было много колонн, естественный свет проникал слабо (к тому же, в большим круглых окнах-розах были установлены темные витражи), и храм был освящен большим количеством настенных и висячих светильников.Огромная люстра с тысячами огней была подвешена на главном куполе и могла подниматься и опускаться при помощи лебедки".

В 1907 г. к собору был пристроен обширный притвор с пятидесятиметровой трехъярусной колокольней под восьмигранным шатровым завершением. Её строительство контролировал В.П. Шаманским, занявшим пост самарского епархиального архитектора после смерти Хилинского в 1905 г., но проект колокольни близко повторяет колокольню Казанской церкви в Верхнем Санчелееве, которую Хилинский построить успел (таким образом, весь мелекесский собор, пусть и построенный в два этапа, можно уверенно называть творением Хилинского). Собор Александра Невского был закрыт последним из храмов Мелекесса, в 1939 году, после чего в нем размещался комсомольский клуб, другие организации и общежития. В 1954 году было постановлено разобрать собор на строительные материалы, и к 1956 году он был полностью уничтожен. Сегодня на месте собора расположен закрытый кинотеатр "Мир". На близлежащей площади Советов в 2007 году была достроена новая церковь Спаса Преображения, выполненная по мотивам утраченного собора.

Широко распространена версия, что автором проекта стал известный столичный архитектор В.О. Шервуд, наиболее известный по зданию Исторического музея на Красной площади и часовне-памятнику гренадерам, героям Плевны. Шервуд при содействии сына Сергея (также архитектора) действительно составил эскизный проект, состоял в переписке с посадским головой К.Г. Марковым и губернатором А.Д. Свербеевым, но в конечном счёте губернское строительное отделение его проект забраковало, чем вызвало немалое возмущение архитектора, к тому времени уже обласканного августейшим вниманием. Точная причина отказа неизвестна, но отсутствие других крупных церковных построек в "портфолио" Шервуда позволяет предположить, что проект был либо слишком неканоничен, либо (что вероятнее) далёк от технического совершенства и слишком сложен в реализации. Формально проект был признан "неудобным к исполнению". В конечном счёте церковь спроектировал самарский губернский архитектор Т.С. Хилинский, работа которого не вызвала каких-либо нареканий.

Более подробно см. в публикации "Храмы-близнецы" Андрея Мокеева, 2014.