Епархия была выделена из Астраханской епархии в 1842 году и тогда именовалась Кавказской и Черноморской. Ко времени открытия епархии (первый епископ — Иеремия (Соловьёв)) в Кавказской области было 126 церквей и 180 причтов, а в Черномории 66 церквей и 96 причтов. За менее чем десятилетний срок пребывания на кафедре была устроена духовная семинария (1846), развёрнуто строительство храмов.

При последнем дореволюционном архиерее митрополите Агафадоре (Преображенском) (на кафедре с 1893 по 1919) особенно развернулась миссионерская работа среди народов Северного Кавказа; в его же бытность в Ставрополе в мае 1919 года состоялся Южно-Русский собор, на котором было образовано Временное Высшее Церковное Управление Юго-Востока России (впоследствии оформившееся как Русская православная церковь заграницей).

В 1920-е — 1930-е года в епархии была разрушена или отобрана у верующих большая часть храмов; в Ставрополе осталась лишь одна Успенская церковь, в то время как до 1917 года православных церквей в городе было более двадцати при населении 45 тысяч человек. С 1936 по 1943 в епархия не существовала.

Послевоенное возрождение церковной жизни в епархии связывается с именем митрополита Антония (Романовского, на кафедре в 1943—1962 гг.). Часть храмов снова была открыта, воссоздана Ставропольская духовная семинария.

После 1988 года количество приходов в епархии увеличилось в четыре раза; была возрождена Ставропольская Духовная семинария, открыты православные общеобразовательные гимназии и школы, детские сады; возрождение проходило в архиерейство поставленного на кафедру 1991 году митрополита Гедеона (Докукина).

28 декабря 1998 года территория Дагестана и Азербайджана вошла в восстановленной тогда Бакинскую и Прикаспийскую епархию.

В 2011 году Кабардино-Балкария, Карачаево-Черкессия и три южных района Ставропольского края переданы Пятигорской епархии, Ингушетия, Северная Осетия, Чеченская Республика тогда же переданы Владикавказской епархии.