Perusahaan ini memulai sejarahnya pada tahun 1963 dengan nama '''NV Vacantie Cord Puntjak'''. Pada tanggal 1817 Juli 1975, perusahaan ini bertransformasi menjadi "PT Patra Jasa". Antara tahun 1988 hingga 1992, Pertamina secara bertahap menyerahkan kepemilikan atas aset yang berupa hotel dan perkantoran ke perusahaan ini. Pada tahun 2014, perusahaan ini berekspansi ke bisnis pengembangan dan pengelolaan properti, serta mendirikan PT Prima Armada Raya untuk berbisnis di bidang penyewaan dan pengawakan kendaraan. Pada tahun 2020, sebagai bagian dari upaya untuk menanggulangi [[pandemi COVID-19]], perusahaan ini membangun ekstensi Rumah Sakit Pertamina Jaya (RSPJ) di hotel miliknya di Jakarta dan membangun ekstensi Rumah Sakit Pertamina Pusat (RSPP) di kompleks Pertamina Simprug.<ref name="annual"/><ref name="profil">{{Cite web|url=https://patra-jasa.com/id/tentang-kami/|title=Tentang Perusahaan|publisher=PT Patra Jasa|language=id|access-date=13 Desember 2021}}</ref>
