Учреждена в 1842 г. (по другим сведениям, в 1843 г.) как Кавказская и Черноморская;

с 1867 г. — Кавказская и Екатеринодарская;

с 1886 г. — Ставропольская и Екатеринодарская;

с 1916 г. — Кавказская и Ставропольская;

с 1922 г. — Ставропольская и Кубанская;

с 1935 г. — Ставропольская и Донская;

с сентября 1943 г. — Ставропольская и Пятигорская;

с мая 1945 г. — Ставропольская и Бакинская;

с февраля 1994 г. — Ставропольская и Владикавказская.

С 1602 г. Северный Кавказ являлся частью Астраханской епархии. В июле 1842 г. из ее состава была выделена епархия, получившая название Кавказской и Черноморской. Новоучрежденная епархия включала в себя приходы Кавказской области (126 церквей и 180 причтов) и Черномории (66 церквей и 96 причтов).

Первый епископ Кавказский Иеремия (Соловьев, 1843-1849 гг.) открыл в 1846 г. семинарию, развернул строительство храмов. Эта работа продолжалась при преемниках, среди которых особо выделяются свт. Игнатий (Брянчанинов; 1857-1862) и свт. Феофилакт (Губин; 1862-1872; местночтимый святой).

В 1885 г. из Ставропольской епархии были выделены приходы Терской области, образовавшие Владикавказскую и Моздокскую епархию в составе Грузинского экзархата (самостоятельная Владикавказская кафедра — с октября 1894 г., упразднена после 1920 г., впоследствии вновь в составе Ставропольской епархии).

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

В 1920-1930 гг. Ставропольская епархия разделила судьбу всей Русской Православной Церкви: за это время сменилось около десяти епископов. В среднем каждый из архиереев занимал кафедру в течение года, после чего подвергался репрессиям. Большая часть храмов была разрушена. В кафедральном г. Ставрополе из более чем 20 православных храмов действующей осталась только Успенская церковь.

Возрождение церковной жизни связано с именем митрополита Антония (Романовского; 1943-1962 гг.) В годы его архипастырства ряд храмов был открыт, возрождена Ставропольская духовная семинария. После включения в состав Ставропольской епархии приходов в Азербайджане она стала именоваться Ставропольской и Бакинской. В годы хрущевских гонений семинария и многие храмы были закрыты. В разное время во главе епархии находились архиепископ Михаил (Чуб; 1962-1968), епископ Иона (Зырянов; 1968-1975), архиепископ Антоний (Завгородний; 1975-1989).

В 1990 г. на кафедру был назначен митрополит Гедеон (Докукин; 1990-2003). В епархии оживилась церковная жизнь: значительно выросло количество приходов (за 20 лет — в четыре раза), была возрождена Ставропольская духовная семинария, открыты православные общеобразовательные гимназии, школы и детские сады.

26 февраля 1994 г. учреждена викарная кафедра в Баку.

Постановлением Священного Синода от 6 октября 1995 г. из состава Ставропольской епархии были выделены приходы Элистинского благочиния, образовавшие Элистинскую и Калмыцкую епархию.

Решением Синода от 28 декабря 1998 г. учреждена Бакинская и Прикаспийская епархия, в которую вошли приходы Азербайджана, Дагестана и Чечни (26 декабря 2003 г. приходы на территории Чеченской Республики были возвращены в Ставропольскую епархию).

В настоящее время епархия включает в себя территории Ставропольского края и северокавказских республик: Кабардино-Балкария, Карачаево-Черкесия, Ингушетия, Северная Осетия — Алания и Чечня.