Территория нынешней Павлодарской области входила в различные епархии Русской Православной церкви: Тобольскую (до 1895 года), Омскую и Семипалатинскую (1895-1911), Омскую и Акмолинскую (1911-1913), Омскую и Павлодарскую (1913-1937), Среднеазиатскую (1938-1947), Семипалатинскую и Павлодарскую (1948-1955), Алма-Атинскую и Казахстанскую (1945-1991), Алма-Атинскую и Семипалатинскую (1991-1999), Астанайскую и Алма-Атинскую (1999-2010).
С 1911 по 1955 годы существовала епископская кафедра (до 1923 года -викарная) в Семипалатинске. В 1928-1937 годы она именовалась Семипалатинской и Усть-Каменогорской, в 1947-1955 годах Семипалатинской и Павлодарской.
Самостоятельная Павлодарская епархия была образована решением Священного Синода от 6 октября 2010 года (журнал № 96) с последующим утверждением на Архиерейском Соборе в пределах Павлодарской и Восточно-Казахстанской областей путем выделения из состава Алма-Атинской епархии. Синод постановил Преосвященному Павлодарскому иметь титул Павлодарский и Усть-Каменогорский.
12 ноября 2010 года в рабочей Патриаршей резиденции в Чистом переулке Святейший Патриарх Кирилл совершил чин наречения архимандрита Варнавы (Сафонова) во епископа Павлодарского и Усть-Каменогорского. А 14 ноября 2010 года в Храме Христа Спасителя Святейший Патриарх Московский и всея Руси Кирилл возглавил хиротонию архимандрита Варнавы (Сафонова) во епископа Павлодарского и Усть-Каменогорского.
Архиерейский Собор Русской Православной Церкви 2-4 февраля 2011 года утвердил решение Священного Синода об образовании Павлодарской епархии (Определение «О вопросах внутренней жизни и внешней деятельности Русской Православной Церкви», п. 3).
5 октября 2011 года, на заседании Священного Синода Русской Православной Церкви было принято решение выделить из состава Павлодарской епархии Усть-Каменогорскую епархию. Епархиальному архиерею Павлодарской епархии определено иметь титул «Павлодарский и Экибастузский».
Храмы епархии.
Благовещенский кафедральный собор города Павлодара
Христорождественский собор города Павлодара
Михаило-Архангельский храм города Павлодара
Иверско-Серафимовский собор города Экибастуза
Воскресенский храм города Аксу
Храм Всех святых в земле Российской просиявших пос. Солнечный
Успенский храм села Успенка
Трехсвятительский храм села Теренколь
Троицкий храм села Железинка
Ильинский храм села Песчаное
Иоанно-Предтеченский храм села Орловка
Александро-Невский храм села Иртышск
Никольский храм пос. Ленинский
Елизаветинский храм села Шарбакты
Петропавловский храм села Павлодарское (при соименном монастыре)
Никольский храм города Аксу
Троицкий храм-часовня села Александровка
Молитвенные дома
Казанский молитвенный дом села Жамбыл
Константино-Еленинский молитвенный дом села Константиновка
Пантелеимоновский молитвенный дом села Башмачное
Казанский молитвенный дом села Жанабет
Часовни
Часовня святителя Николая Чудотворца
Часовня во имя Всех святых (на Суворовском кладбище города Павлодара)
Часовня Смоленской иконы Божией Матери в селе Теренколь
Воскресенская часовня в селе Песчаное