Главный престол был освящён во имя святого благоверного великого князя Александра Невского, правый придел — во имя Архистратига Михаила, левый — во имя святителя Николая Чудотворца.
Первоначальный проект храма был составлен в 1866 году архитектором Давидом Гриммом. 6-го апреля 1871 года состоялась торжественная закладка. Строительство продолжалось долгое время. В 1890 году первоначальный план постройки был изменён, на той же Гунибской площади было избрано другое место для его сооружения. В 1891 году было завершено сооружение фундамента и началось строительство самого здания. Строительством руководил инженер-полковник В. П. Герасимов. Торжественное освящение храма состоялось 21 мая 1897 года.
Собор представлял собой восьмикупольный храм с отдельно стоявшей колокольней. Вмещал до 1000 человек. Внутри был освещён электричеством и украшен щитами с перечнями частей войск, участвовавших в покорении Кавказа, и их знамёнами. Стены собора были покрыты живописными изображениями и орнаментом. Расписывали храм местные художники Колчин и Лонго.
Разрушен по указанию Берии в 1930 году. На его месте был построен Дом Правительства (в настоящее время — здание Парламента Грузии).
