В 1859 году на углу улиц Никольской (Аблова) и Щепной (Самарская) на добровольные пожертвования населения Мелекесского Завода, уставшего ходить в церковь в соседний Русский Мелекесс, была построена деревянная православная церковь во имя святого Николая Чудотворца. Благодаря этому событию Мелекесс стал селом, а площадь возле храма стала именоваться Никольской.
Но, к несчастью, в 1889 году в Мелекессе был большой пожар при котором сгорела и церковь, и близлежащие торговые ряды, и множество домов. На месте сгоревшей церкви решили построить Храм во имя Александра Невского (в память убитого царя-освободителя Александра II), что и сделали на народные деньги, по проекту архитектора Хилинского Т.С., перенеся место на соседнюю улицу Большую (III Интернационала). Освятили 19 декабря 1893 года (1 января 1894 года).
В 1907 году к храму пристроили колокольню. Место позади храма было отдано под храмовые нужды, там был разбит церковный сад, появились захоронения.
В 30-е годы богослужение в храме было запрещено и храм использовали и под клуб и под склады, а на колокольне пожарные устроили обзорную площадку для наблюдения за городом.
В бывшем церковном саду устроили детский парк.
В 1954 году из-за якобы «ветхости и аварийного состояния» храм решили уничтожить. Разобрали по кирпичику. А на его фундаменте построили кинотеатр «Мир».
С 90-х годов кинотеатр не работает, здание продали коммерсантам.
Валерий Гордеев писал, что при разборе храма кто-то нашел медную доску, которую заложили при его постройке с надписями: когда и во имя кого этот храм строили, и унес домой, спас от поругания.
Ныне здание пустует, а парк по неведомой логике назвали «Марковым садом».