Первоначально Екатеринославская епархия делилась на семь духовных правлений: Кременчугское, Полтавское, Кобелякское, Елисаветградское, Новомиргородское, Славянское и Херсонское. В 1776–1777 гг. на территории Азовской губернии было учреждено ещё пять духовных правлений: Екатеринославское, Самарское (существовало до 1778 г.), Бахмутское, Павловско-Павлоградское и Новоростовское. 7 марта 1787 г. для управления храмами на юге епархии и в Крыму было учреждено Феодосийское и Мариупольское викариатство Екатеринославской епархии с центром в городе Старый Крым (упразднено 16 октября 1799 г.). Первоначальная история епархии тесно связана с историей Новороссийского края, начальником которого после подписания 10 июля 1774 г. Кючюк-Кайнарджийского мира с Турцией стал князь Григорий Александрович Потёмкин. Третий Екатеринославский епископ – Амвросий (Серебреников; 1786–1792 гг.) сопровождал армию князя Г.А. Потёмкина в Русско-турецкой войне 1787–1791 гг., после занятия русскими войсками Молдавии по ходатайству Г.А. Потёмкина в 1789 г. епископ Амвросий был назначен местоблюстителем Молдо-Влахийского экзархата. Будучи в Молдавии, архиерей посетил Новонямецкий монастырь и возвёл в сан архимандрита подвизавшегося в нём Паисия (Величковского). Ко времени учреждения епархии на её территории действовали 232 церкви, несколько монастырей. Ближайшими к Екатеринославу были Самарский Пустынный во имя Николая Чудотворца мужской монастырь, полтавский в честь Воздвижения Креста Господня, в котором жили Екатеринославские архиереи до перевода кафедры в 1798 г. в Новомиргород, Сокольский мужской монастырь в честь Преображения Господня близ города Кобеляки (основан в 1714 г., упразднён в 1786 г.), 11 часовен, клир епархии составляли 1476 священно- и церковнослужителей. Обширная новоучреждённая епархия нуждалась в храмах, практически отсутствовавших в пределах Азовской губернии. В 1774 г. Киевский митрополит благословил строить в Новоселице (современный город Новомосковск) деревянный трёхпрестольный храм во имя Святой Троицы на месте обветшавшей однопрестольной церкви с таким же посвящением. Храм был заложен 2 июня 1775 г., в 1778 г. освящён архиепископом Евгением, приделы (во имя апостолов Петра и Павла и святителей Василия Великого, Григория Богослова и Иоанна Златоуста) были освящены 12 августа 1780 г. 6 сентября 1780 г. в крепости Новый Кайдак (Новый Кодак), неподалёку от Екатеринослава, был заложен храм в честь Сошествия Святого Духа на апостолов. В 1781–1783 гг. в Старом Кайдаке (Старом Кодаке) строилась деревянная церковь во имя апостолов Петра и Павла, сгоревшая за несколько дней до освящения. В 1784 г. в епархии насчитывалось 424 храма, 1394 священно- и церковнослужителя. В 1788 г. был освящён собор в честь Покрова Пресвятой Богородицы в Александровске. Началось храмоздательство и в основанном в 1775 г. Екатеринославе. Первоначально город располагался на месте села Лошаковка, при впадении реки Кильчень в реку Самару (Екатеринослав I, или Кильченский). В 1780–1781 гг. здесь была построена церковь в честь Казанской иконы Божьей Матери (в 1791 г. перевезена в Екатеринослав II).