Perusahaan ini didirikan oleh Pertamina pada bulan Februari 1997 dengan nama PT Elnusa Harapan, dengan bisnis awalnya di bidang penyimpanan, pengangkutan, dan penjualan BBM. Pada tahun 2004, nama perusahaan ini diubah menjadi PT Patra Niaga, dan pada tahun 2012, nama perusahaan ini diubah menjadi seperti sekarang. Pada tahun 2014, perusahaan ini mulai mengembangkan "Patra Batu Bintang Commercial Estate" di Dumai.
Pada tahun 2020, perusahaan ini ditunjuk sebagai induk subholding Komersial & Perdagangan di lingkungan Pertamina, yang beranggotakan PT Pertamina Lubricants, PT Pertamina Retail, dan Pertamina International Marketing & Distribution Pte Ltd.[4][5] Pada bulan Agustus 2021, BPH Migas resmi mengalihkan penugasan penyediaan dan pendistribusian solar bersubsidi, Premium, dan minyak tanah dari Pertamina ke perusahaan ini sesuai dengan Peraturan Presiden nomor 69 tahun 2021.[6]
