Benteng Oranje sebelumnya merupakan tempat yang terbengkalai bernama Benteng Melayu milik Sultan Ternate. Sultan Ternate menghadiahi benteng tersebut kepada VOC, setelah VOC berhasil mengusir bangsa Spanyol dari Ternate.
Bersamaan dengan itu, VOC mendapat izin dari Sultan Ternate untuk memonopoli perdagangan cengkeh di wilayahnya. Oleh seorang Laksamana bernama François Wittert, Benteng Melayu dibenahi dan diganti namanya menjadi Benteng Oranje pada tahun 1605.
Gubernur-Jenderal pertama Hindia Belanda, Pieter Both, pernah menggunakan benteng tersebut untuk berunding dengan Sultan Mudaffar dari Ternate, setelah perusahaan VOC menetapkan wilayah Maluku Utara sebagai lokasi pusat pemerintahan Hindia Belanda yang telah mereka dirikan.
Selain itu, Pahlawan Nasional Sultan Mahmud Badarudin II dari Palembang dan keluarganya pernah diasingkan di Benteng Oranje tahun 1822.
Risiko yang harus diterima dari perjuangan panjangnya dalam membebaskan tanah Palembang dari tangan Belanda. Sampai akhir hayatnya, beliau dimakamkan tidak jauh dari Benteng Oranje.
