Sejarah berdirinya PT PELNI bermula dengan dikeluarkannya Surat Keputusan Bersama (SKB) antara Menteri Perhubungan dan Menteri Pekerjaan Umum tanggal 5 September 1950 yang isinya mendirikan Yayasan Penguasaan Pusat Kapal-kapal (PEPUSKA).
Latar belakang pendirian Yayasan PEPUSKA diawali dari penolakan pemerintah Belanda atas permintaan Indonesia untuk mengubah status maskapai pelayaran Belanda yang beroperasi di Indonesia, N.V. K.P.M (Koninklijke Paketvaart Matschappij) menjadi Perseroan Terbatas (PT). Pemerintah Indonesia juga menginginkan agar kapal-kapal KPM dalam menjalankan operasi pelayarannya di perairan Indonesia menggunakan bendera Merah Putih. Pemerintah Belanda dengan tegas menolak semua permintaan yang diajukan oleh pemerintah Indonesia.
Dengan modal awal 8 (delapan) unit kapal dengan total tonage 4.800 DWT (death weight ton), PEPUSKA berlayar berdampingan dengan armada KPM yang telah berpengalaman lebih dari setengah abad. Persaingan benar-benar tidak seimbang ketika itu, karena armada KPM selain telah berpengalaman, jumlah armadanya juga lebih banyak serta memiliki kontrak-kontrak monopoli.
Akhirnya pada 28 April 1952 Yayasan Pepuska resmi dibubarkan. Pada saat yang sama didirikanlah PT PELNI dengan berdasarkan Surat Keputusan Menteri Perhubungan Nomor M.2/1/2 tanggal 28 Februari 1952 dan No. A.2/1/2 tanggal 19 April 1952, serta Berita Negara Republik Indonesia No. 50 tanggal 20 Juni 1952. Sebagai Presiden Direktur Pertamanya diangkatlah R. Ma'moen Soemadipraja (1952-1955).
Delapan unit kapal milik Yayasan Pepuska diserahkan kepada PT PELNI sebagai modal awal. Karena dianggap tidak mencukupi maka Bank Ekspor Impor menyediakan dana untuk pembelian kapal sebagai tambahan dan memesan 45 "coaster" dari Eropa Barat. Sambil menunggu datangnya "coaster" yang dipesan dari Eropa, PELNI mencarter kapal-kapal asing yang terdiri dari berbagai bendera. Langkah ini diambil untuk mengisi trayek-trayek yang ditinggalkan KPM. Setelah itu satu persatu kapal-kapal yang dicarter itu diganti dengan "coaster" yang datang dari Eropa. Kemudian ditambah lagi dengan kapal-kapal hasil pampasan perang dari Jepang.
Status PT PELNI mengalami dua kali perubahan. Pada tahun 1961 pemerintah menetapkan perubahan status dari Perusahaan Perseroan menjadi Perusahaan Negara (PN) dan dicantumkan dalam Lembaran Negara RI No. LN 1961. Kemudian pada tahun 1975 status perusahaan diubah dari Perusahaan Negara (PN) menjadi Perseroan terbatas (PT) PELNI sesuai dengan Akte Pendirian No. 31 tanggal 30 Oktober 1975. Perubahan tersebut dicantumkan dalam Berita Negara RI No. 562-1976 dan Tambahan Berita Negara RI No. 60 tanggal 27 Juni 1976.
Seiring dengan perjalanan waktu dan perkembangan usaha, perusahaan mengalami beberapa kali perubahan bentuk Badan Usaha. Pada tahun 1975 berbentuk Perseroan sesuai Akta Pendirian Nomor 31 tanggal 30 Oktober 1975 dan Akte Perubahan Nomor 22 tanggal 4 Maret 1998 tentang Anggaran Dasar PT. Pelni yang diumumkan dalam Berita Negara Republik Indonesia tanggal 16 April 1999 Nomor 31 tambahan Berita Negara Nomor 2203
MILESTONE PT PELNI (PERSERO)
4 September 1888 - Berdirinya Koninklijke Paketvaart Maatschappij (NV K.P.M.)
Pada tahun 1888 terbentuk suatu Maskapai Pelayaran baru di negeri Belanda dengan nama: Koninklijke Paketvaart Maatschappij (NV K.P.M.). Tujuan sesungguhnya dari pendirian K.P.M. ini adalah bukan semata-mata untuk kepentingan Ekonomi atau perdagangan semata. Oleh pemerintah Hindia Belanda, K.P.M. dimaksudkan sebagai aparat angkutan yang terpusat (Central Vervoers Apparaat).
1 Januari 1931 - Groot Archipel Contract
Perjajian antara Pemerintah Hindia-Belanda dengan Koninklijke Paketvaart Maatschappij (NV K.P.M.)
5 September 1950 - Pendirian Yayasan Penguasaan Kapal-Kapal (PEPUSKA)
Pemerintah Indonesia melalui Surat Keputusan Menteri Perhubungan dan Menteri Pekerjaan Umum No. 3260/Ment tertanggal 5 September 1950 mendirikan Yayasan Penguasaan Kapal-Kapal (PEPUSKA) sedangkan Stiching Gemeenschappelijk Scheppenbezit (S.G.S) dibubarkan.
28 April 1952 - Pendirian PT PELNI (Pelayaran Nasional Indonesia)
PT PELNI (Pelayaran Nasional Indonesia) didirikan pada tanggal 28 April 1952 di Jakarta berdasarkan SK. Menteri Perhubungan Ir. R. Djuanda nomor 2/1/2 tanggal 23 Februari 1952 yang seluruh kepemilikannya oleh Pemerintah/Negara. Dengan Direktur Utama dan sebagai pendiri PELNI atas nama Pemerintah adalah Mr. Ma’moen Soemadipradja dan R. Soena Soerapoetra.
10 Oktober 1956 - KM TAMPOMAS Tiba di Indonesia
Pemerintah Indonesia melalui Jawatan Pelayaran bermaksud untuk mengganti kapalkapal milik milik KPM. Atas bantuan dana dari Pemerintah Belanda dibangunlah KM Tampomas. Pembuatannya dimulai pada tahun 1955 dengan peletakan lunas di Galangan KON MY DE SCHELDE berlokasi di Vlisingen Nederland. Pelayaran perdana KM Tampomas pada 12 Oktober 1956, mengitari Gunung Krakatau di Selat Sunda dengan membawa Menteri Pelayaran dan para undangan terhormat lainnya. KM Tampomas dinakhodai oleh Capt. Marsman dan KKM Carol Schietsinger.
20 Maret 1958 - Berhenti beroperasinya KPM di Indonesia
Pada tanggal 20 Maret 1958 tamatlah riwayat NV K.P.M. dengan dikeluarkannya Keputusan Pemerintah No.23/1958 yang melarang kapal-kapal KPM untuk mengarungi perairan Indonesia serta menempatkan KPM dibawah pengawasan Pemerintah Republik Indonesia.
1961 - Perubahan Status PELNI dari PT menjadi PN (Perusahaan Negara)
Berdasarkan Peraturan Pemerintah Pengganti Undang-undang No.19/1960 dan menjadi Undang-undang No.1/1961, maka Perusahaan yang dibentuk oleh Pemerintah atau Perusahaan Belanda yang dibawah pengawasan Pemerintah Republik Indonesia statusnya berubah menjadi Perusahaan Negara (PN).
17 Maret 1973 - PT PELNI Menjadi Persero, PT PELNI (Persero)
Berdasarkan Perarturan Pemerintah No.9/1973: Peraturan Pemerintah tentang Perusahaan Negara. Tanggal 17 maret 1973 PELNI dialihkan kembali menjadi Perusahaan Persero. Dari PN PELNI Menjadi PT PELNI.
1983 - Pengadaan Kapal Penumpang buatan Jerman
Kehadiran kapal-kapal penumpang PELNI merupakan buatan dari Galangan Jos L. Meyer. Ketika itu Jos L. Meyer membangun lima kapal baru yaitu: KM Watampone - KM Watudambo - KM Warisano - KM Wakolo - KM Wandebori Paket pertama pembangunan kapal di galangan Jos L. Meyer ini berjumlah 16 unit, diserahkan secara bertahap dari tahun 1983 hingga 1996.
17 Juni 1993 - Peresmian KM Ciremai oleh Presiden RI Soeharto
Pada tanggal 17 Juni 1993, Presiden Republik Indonesia Soeharto meresmian pengoperasian KM Ciremai di Cirebon.
11 Mei 2023 - Pergantian Logo dan Tagline PT PELNI (Persero)
Di tahun 2023 PT PELNI (Persero) melakukan banyak transformasi, salah satunya adalah perubahan logo dan tagline perusahaan menjadi “We Connect, We Unify”. Acara seremoni pergantian logo dan tagline dilaksanakan berbarengan dengan perayaan puncak Hari Ulang Tahun PELNI yang ke-71.
