В 1902 году архитектор Фёдор Вержбицкий разработал типовой проект гарнизонного храма, предназначенного для строительства в различных городах Туркестанского края, включая Самарканд. Этот проект был адаптирован военным инженером Фёдором Смирновым для местных условий. Торжественная закладка храма состоялась в 1909 году, а к осени 1911 года основные строительные работы были завершены. В 1912 году храм был освящён в честь святителя Алексия, митрополита Московского.
Архитектурно собор представляет собой зальное сооружение с неразделённым пространством размером 24 на 16 метров и глубоким алтарём, увенчанным высоким светлым куполом. Над западным входом возвышается восьмигранная колокольня. Здание выполнено в русском стиле с минимальным декором, что подчёркивает его строгость и монументальность.
В 1920-х годах, в период антирелигиозной политики советской власти, собор был закрыт, а его купол и колокольня демонтированы. Здание использовалось для различных нужд, включая размещение танцевальной площадки, столовой и склада. В 1980-х годах, после вывода воинской части, здание перешло на баланс государственного музея-заповедника.
В 1996 году, в преддверии празднования 125-летия Ташкентской и Среднеазиатской епархии, собор был возвращён Русской Православной Церкви. 13 ноября того же года Патриарх Московский и всея Руси Алексий II совершил чин повторного освящения храма. С этого момента начались восстановительные работы, направленные на возвращение собору его первоначального облика и функций.
