Епархия была выделена из Астраханской епархии в 1842 году и тогда именовалась Кавказской и Черноморской. Ко времени открытия епархии (первый епископ — Иеремия (Соловьёв)) в Кавказской области было 126 церквей и 180 причтов, а в Черномории 66 церквей и 96 причтов. За менее чем десятилетний срок пребывания на кафедре была устроена духовная семинария (1846), развёрнуто строительство храмов.
При последнем дореволюционном архиерее митрополите Агафадоре (Преображенском) (на кафедре с 1893 по 1919) особенно развернулась миссионерская работа среди народов Северного Кавказа; в его же бытность в Ставрополе в мае 1919 года состоялся Южно-Русский собор, на котором было образовано Временное Высшее Церковное Управление Юго-Востока России (впоследствии оформившееся как Русская православная церковь заграницей).
В 1920-е — 1930-е года в епархии была разрушена или отобрана у верующих большая часть храмов; в Ставрополе осталась лишь одна Успенская церковь, в то время как до 1917 года православных церквей в городе было более двадцати при населении 45 тысяч человек. С 1936 по 1943 в епархия не существовала.
Послевоенное возрождение церковной жизни в епархии связывается с именем митрополита Антония (Романовского, на кафедре в 1943—1962 гг.). Часть храмов снова была открыта, воссоздана Ставропольская духовная семинария.
После 1988 года количество приходов в епархии увеличилось в четыре раза; была возрождена Ставропольская Духовная семинария, открыты православные общеобразовательные гимназии и школы, детские сады; возрождение проходило в архиерейство поставленного на кафедру 1991 году митрополита Гедеона (Докукина).
28 декабря 1998 года территория Дагестана и Азербайджана вошла в восстановленной тогда Бакинскую и Прикаспийскую епархию.
В 2011 году Кабардино-Балкария, Карачаево-Черкессия и три южных района Ставропольского края переданы Пятигорской епархии, Ингушетия, Северная Осетия, Чеченская Республика тогда же переданы Владикавказской епархии.
Прежние наименования Епархии
Кавказская и Черноморская (17 июля 1842 — 30 июля 1867)
Кавказская и Екатеринодарская (30 июля 1867 — 8 марта 1886)
Ставропольская и Екатеринодарская (8 марта 1886 — 5 октября 1916)
Кавказская и Ставропольская (5 октября 1916—1922)
Ставропольская и Кубанская (1922—1934)
Ставропольская и Донская (1935—1943)
Ставропольская и Пятигорская (1943—1945)
Ставропольская и Бакинская (1945—1994)
Ставропольская и Владикавказская (1994—2011)
Ставропольская и Невинномысская (с 22 марта 2011)
Хронологический список епархиальных архиереев
Иеремия (Соловьёв) (1 января 1843 — 20 ноября 1849)
Иоанникий (Образцов) (20 ноября 1849 — 30 октября 1857)
Игнатий (Брянчанинов) (13 ноября 1857 — 5 августа 1861)
Феофилакт (Губин) (1 декабря 1862 — 11 мая 1872)
Герман (Осецкий) (24 июня 1872 — 16 февраля 1886)
Владимир (Петров) (8 апреля 1886 — 25 ноября 1889)
Евгений (Шерешилов) (16 декабря 1889 — 17 июля 1893)
Агафодор (Преображенский) (17 июля 1893 — 31 июля 1919)
Михаил (Космодемьянский) (10 мая — 1 сентября 1914, 1919—1923) в первый раз — в/у, еп. Александровский
Димитрий (Добросердов) (26 апреля — июнь 1923)
Евсевий (Рождественский) (1923)
Иннокентий (Летяев) (28 октября 1923 — 20 августа 1926)
Иринарх (Синеоков-Андреевский) (октябрь — декабрь 1926)
Иннокентий (Ястребов) (1926—1927)
Арсений (Смоленец) (1 ноября — 25 ноября 1927)
Серафим (Мещеряков) (10 февраля 1928 — 24 августа 1933)
Лев (Черепанов) (24 августа 1933—1934)
Антоний (Романовский) (1935—1936) в/у, еп. б. Донской
Антоний (Романовский) (27 сентября 1943 — 7 ноября 1962)
Виктор (Святин) (7 — 16 ноября 1962) в/у, митр. Краснодарский
Михаил (Чуб) (16 ноября 1962 — 27 февраля 1968)
Иона (Зырянов) (27 февраля 1968 — 1 июля 1975)
Антоний (Завгородний) (3 августа 1975 — 4 декабря 1989)
Гедеон (Докукин) (26 января 1990 — 21 марта 2003)
Исидор (Кириченко) (26 декабря 2002 — 7 мая 2003) в/у митр. Екатеринодарский
Феофан (Ашурков) (7 мая 2003 — 22 марта 2011)
Кирилл (Покровский) (с 22 марта 2011)
