Kekristenan di wilayah Sumatera telah dimulai sejak abad VII. Para ahli sejarah menandai era tersebut dengan berdirinya sebuah gereja di daerah Barus, Tapanuli Tengah, sekitar tahun 645.

Lalu, sejak kapankah benih-benih Gereja Katolik tersemai di bumi Sumatera Selatan?

Sejarah Gereja Katolik Sumatera Selatan, mulai ditorehkan sejak tahun 1887, ketika seorang misionaris Serikat Yesus, Pastor J. van. Meurs, S.J. (Lahir 03 Februari 1838 di Amsterdam),  yang sebelumnya berkarya di Langowan, Minahasa, Sulawesi Utara mengawali langkah besarnya di sebuah dusun kecil bernama Tanjung Sakti, wilayah Pasemah, Ulu Manna, karesidenan Bengkulu.

Tahun 1890 benih ‘kekatolikan’ mulai bersemi. Pastor van Meurs, SJ berhasil mempermandikan 8 anak dan 3 anak menjadi katekumen. Agar pelayanan pastoral di daerah misi lebih intensif, Bruder Vester ikut ambil bagian dalam tugas pelayanan, pada bulan Maret 1891.

Pastor van Meurs yang menderita sakit keras dipindah ke Sukabumi dan pada tanggal 06 Agustus 1891, ia meninggal dunia di sana. Pada tahun 1892, Bruder Vester pindah ke Maumere-Flores.

Bulan Juni 1894, Pastor W.L. Jannisen, S.J. bersama Bruder Zinken datang ke Tanjung Sakti, untuk melanjutkan karya para pendahulu. Umat telah berkembang menjadi 200 orang; dan pada tahun 1897 terjadi penerimaan Sakramen Penguatan untuk pertama kalinya oleh Mgr. Staal dari Batavia.

Meski memiliki harapan yang cerah dan menjanjikan, karya misi di Tanjung Sakti dihentikan. Bulan November 1898, Pastor Jannisen dipindahkan ke Padang. Beliau masih tetap mengunjungi umat Tanjung Sakti beberapa kali dalam setahun, untuk meneguhkan iman mereka. Dari Tanjung Sakti sebagai pos utama, karya misi meluas ke Karesidenan Bengkulu, Palembang, dan sekitarnya.

Tanggal 30 Juni 1911, Roma mengeluarkan dekrit tentang pemisahan Prefektur Apostolik Sumatera (yang berpusat di Padang) dari Vikariat Apostolik Batavia. Prefek Apostolik pertama adalah Mgr. Liberatus Cluts, OFM Cap. Beliau mengemban tugas ini sejak tahun 1912-1921.

Masa-masa yang sulit bagi jemaat perdana, terjadi sekitar tahun 1914, ketika pengaruh agama lain menggerus iman umat Katolik Tanjung Sakti. Gembala umat saat itu, Pastor Sigebertus OFM Cap, dibantu Mr. J.C. Kielstra dan tujuh suster Kongregasi Belas Kasih berjuang keras membendung gelombang perpindahan iman.

Bulan Agustus 1920, Pastor Mathias Brans tiba di Tanjung Sakti menggantikan Pastor Sigebertus yang dipindahtugaskan ke Padang. Tahun-tahun terakhir masa kekaryaan pastor-pastor Kapusin di Tanjung Sakti, keadaan semakin membaik. Karya misi imam-imam Kapusin berakhir setelah imam-imam Kongregasi Hati Kudus Yesus (SCJ) datang ke Tanjung Sakti.

Sesuai dengan ‘breve’ dari Roma bertanggal 27 Desember 1923, Sumatera Selatan dipisahkan dari Prefektur Apostolik Sumatera (yang kemudian berubah menjadi Prefektur Apostolik Padang).

Wilayah Sumatera Selatan berubah statusnya menjadi Prefektur Apostolik Bengkulu. Nama ini dipilih karena Tanjung Sakti yang merupakan pos utama misi,  terletak di wilayah Karesidenan Bengkulu.

Tanggal 28 Mei 1926, Mgr. H.L. Smeets, SCJ diangkat menjadi Prefektur Apostolik Bengkulu. Bulan September 1924, para misionaris SCJ yang pertama, tiba di Tanjung Sakti. Mereka adalah Pastor H.J.D. van Oort, SCJ; Pastor K. van Stekelenburg, SCJ dan Bruder Feliks van Langenberg, SCJ. Lima pos karya misi saat itu adalah Tanjung Sakti, Palembang, Bengkulu, Tanjung Karang-Teluk Betung, dan Jambi.

Pastor Harrie van Oort, SCJ menggantikan Mgr. Harrie Smeets, SCJ yang kembali ke Eropa, tanggal 19 Januari 1927. Tanggal 19 Januari 1934,  jabatan Prefektur Apostolik beralih ke pundak Pastor Mekkelholt.

Vikariat Apostolik Palembang, ditetapkan pada tanggal 13 Juni 1939, sebagai pengembangan Prefektur Apostolik Bengkulu. Vikaris Apostolik masa itu adalah Mgr. Henri Martin Mekkelholt, SCJ.

Dampak Perang Dunia II yang berkecamuk antara tahun 1939 – 1945, sangat dirasakan oleh Gereja. Di wilayah Palembang, banyak umat meninggalkan imannya. Banyak imam, biarawan dan biarawati yang menjadi korban perang. Setelah Perang Dunia II berakhir, situasi Vikariat Apostolik Palembang relatif lebih aman dibandingkan masa-masa sebelumnya. Bulan November - Desember 1947, Pastor Hermelink, Bruder Caspar dan para Suster Carolus Borromeus meneruskan kembali karya pastoral di Lahat.

Tanggal 19 Juni 1952, Tahta Suci menetapkan daerah misi Lampung ditetapkan sebagai Prefektur Apostolik yang terpisah dari Vikariat Apostolik Palembang.

Hirarkhi Gerejani Indonesia terbentuk pada tanggal 3 Januari  1961. Vikariat Apostolik Palembang berubah statusnya menjadi Keuskupan Palembang; dan Mgr. Henri Martin Mekkelholt, SCJ diangkat sebagai Uskup pertama. Karena kesehatan beliau menurun, Mgr. Mekkelholt memohon seorang uskup pembantu kepada Tahta Suci.

Permohonan itu dikabulkan. Pastor J.H. Soudant, SCJ dipilih sebagai Uskup Coadjutor dan ditahbiskan sebagai uskup pada tanggal 29 Juni 1961. Setelah Mgr. H.M. Mekkelholt meletakkan jabatan sebagai uskup Palembang, Mgr. J.H. Soudant, SCJ meneruskan tugas penggembalaan Keuskupan Palembang sejak 5 April 1963 - 20 Mei 1997.

Pada masa kepemimpinan Mgr. J.H. Soudant, SCJ, seturut keputusan Tahta Suci ditahbiskanlah seorang Uskup Pembantu. Beliau adalah Mgr. Aloysius Sudarso, SCJ. Setelah Mgr. Soudant memasuki masa purna jabatan, 20 Mei 1997, Mgr. Al. Sudarso, SCJ ditetapkan sebagai Uskup Palembang.

Akhirnya sampailah pada saat yang penuh rahmat. Pada tanggal 1 Juli 2003, Yang Mulia Bapa Suci Paus Yohanes Paulus II, melalui surat kabar Vatikan L’osservatore Romano mengumumkan hal-hal berikut :

1. Bapa Suci berkenan mendirikan satu Provinsi Gerejawi Baru di Sumatera, yaitu Keuskupan Agung Palembang.
2. Bapa Suci telah berkenan menunjuk Mgr. Aloysius Sudarso, SCJ menjadi Uskup Metropolitan pertama untuk Keuskupan Agung Palembang.

Wilayah Keuskupan Agung Palembang mencakup tiga propinsi, yakni Sumatera Selatan, Jambi dan Bengkulu. Dua keuskupan sufragan dari Keuskupan Agung Palembang adalah : Keuskupan Tanjung Karang dan Keuskupan Pangkal Pinang.

Pada tanggal 03 Juli 2021, Paus Fransiskus mengumumkan pengangkatan Mgr. Yohanes Harun Yuwono untuk menggembalakan umat Keuskupan Agung Palembang menggantikan Mgr. Aloysius Sudarso, SCJ yang permohonannya terkait pengunduran diri sebagai Uskup Agung Keuskupan Agung Palembang telah diterima Paus. Pada hari Minggu, 10 Oktober 2021, umat beriman Keuskupan Agung Palembang mengikuti dengan khidmat instalasi Uskup Agung Mgr. Yohanes Harun Yuwono di Gereja St. Yoseph Palembang secara daring dan luring.