После распада Албанского государства во время арабского вторжения в городе Дербенте вплоть до XVIII века не оставалось действующих христианских храмов. До 40-х годов ХIХ века единственной православной церковью, удовлетворявшей потребности военного населения города, являлась церковь при линейном батальоне, временно разместившаяся в старом здании бывшей мечети (ныне Кильса-мечеть).
С ростом русскоязычного населения в начале ХIХ века стал насущным вопрос о возведении нового православного храма в городе Дербенте. Решение возникшей проблемы было возложено на губернского начальника князя А.И.Гагарина. Под руководством инженера капитана В. И. Гершельмана начались строительные работы по проекту флигель-адъютанта полковника Г. Г. Гагарина. Закладка фундамента храма производилась 8 мая 1849г. в 12 часов дня в присутствии князя и княгини Воронцовых. Место для строительства церкви выбрано совсем не случайно. По мнению многих исследователей в IVB. здесь находился албанский христианский храм. Действительно, при рытье фундамента для новой церкви обнаружены руины прежнего храма. Было выявлено много глиняных труб и остатки бассейна, а также почти уцелевшие своды храма из жжённого кирпича с остатками колонн и полов, вымощенных плитами. При ранних христианских храмах строили так называемые баптистерии — здания с бассейнами, где совершалось таинство крещения.
Новый храм, исполненный по проекту флигель — адъютанта полковника князя Гагарина, был рассчитан на 500 человек и представлял собой изящный образец византийской архитектуры. В книге «История города Дербента» Е. И. Козубского даётся следующее его описание: «Храм был построен из гладкотёсанного камня, пол — торцовый из орехового дерева, очень красивый и устранявший гул, в 1859г. было разрешено устроить чугунный пол. Паникадило из накладного серебра о 36 свечах в 3 яруса было сделано в Москве мастером Пецом.
Пароходом из Астрахани был доставлен колокол для церкви весом в 113 пудов 15 фунтов». По ходатайству князя Аргутинского была разрешена «покупка и поставка башерных часов мастера Штерна из Одессы ценою 1684 рублей 12 коп». Внутри церкви обращали на себя внимание три иконы, написанные князем Г. Г. Гагариным — «Тайная вечеря», «Святой архангел Михаил» и «Святой архангел Гавриил».
26 ноября 1853г. было совершено освящение церкви во имя святого Георгия Победоносца. Служба в церкви началась с 15 декабря 1853г.
Первое православное культовое сооружение Дагестана ХIХ века было возведено на площади Ермолова (ныне площадь Свободы). В настоящее время на месте одной из красивейших церквей Кавказа, разрушенной в 1938 году, находится памятник В.И.Ленину.