Benteng vredeburg pertama kali dibangun pada tahun 1760 atas perintah dari Sri Sultan Hamengku Buwono I dan permintaan pihak pemerintah Belanda yang saat itu dipimpin oleh Nicholaas Harting yang menjabat sebagai Gubernur Direktur Pantai Utara Jawa. Adapun dalih awal tujuan pembangunan benteng ini adalah untuk menjaga kemananan keratin. Akan tetapi, maksud sebenarnya dari keberadaan benteng ini adalah untuk memudahkan pengawasan pihak Belanda terhadap segala kegiatan yang dilakukan pihak keraton Yogyakarta. Pembangunan benteng pertama kali hanya mewujudkan bentuk sederhana, yaitu temboknya yang ahnya berbahankan tanah, ditunjang dengan tiang-tiang yang terbuat dari kayu pohon kelapa dan aren, dengan atap ilalang. Bangunan tersebut dibangun dengan bentuk bujur sangkar yang di keempat ujungnya dibangun seleka atau bastion. Oleh Sri Sultan HB IV, keempat sudut itu diberi nama Jaya Wisesa (sudut barat laut), Jaya Purusa(sudut timur laut), Jaya Prakosaningprang (sudut barat daya), dan Jaya Prayitna (sudut tenggara).
Kemudian pada masa selanjutnya, gubernur Belanda yang bernama W.H. Van Ossenberg mengusulkan agar benteng ini dibangun lebih permanen dengan maksud kemanan yang lebih terjamin. Kemudian pada tahun 1767, pembangunan benteng mulai dilakukan di bawah pengawasan seorang arsitek Belanda bernama Ir. Frans Haak dan pembangunannya selesai pada tahun 1787. Setelah pembangunan selesai, benteng ini diberi nama “Rustenburg” yang berarti benteng peristirahatan. Pada tahun 1867, terjadi gempa hebat di Yogyakarta dan mengakibatkan banyak bangunan yang runtuh, termasuk Rustenburg. Kemudian, segera setelahnya diadakan pembangunan kembali benteng Rustenburg ini yang kemudian namanya diganti menjadi “Vredeburg” yang berarti benteng perdamaian. Hal ini sebagai wujud simbolis manifestasi perdamaian antara pihak Belanda dan Keraton.
Secara historis, sejak awal pembangunan hingga saat ini, terjadi beberapa kali perubahan status kepemilikan dan fungsi benteng, yang antara lain:
- Tahun 1760-1765, pada awal pembangunannya status tanah tetap atas nama milik Keraton, tetapi penggunaannya di bawah pengawasan Nicolaas Harting, Gubernur Direktur wilayah Patai Utara Jawa.
- Tahun 1765-1788, status tanah secara formal tetap milik Keraton, tetapi penguasaan benteng dan tanahnya dipegang oleh Belanda di bawah Gubernur W.H. Ossenberg.
- Tahun 1788-1799, status tanah tetap milik keratin, kemudian pada masa ini, benteng digunakan secara sempurna oleh VOC.
- Taghun 1799-1807, status tanah secara formal tetap milik Keraton, dan penggunaan benteng secara de facto menjadi milik pemerintah Belanda di bawah pemerintahan Gubernur Van De Burg.
- Tahun 1807-1811, secara formal tanah tetap milik Keraton, dan penggunaan benteng secara de factomenjadi milik pemerintah Belanda di bawah pemerintahan Gubernur Daendels.
- Tahun 1811-1816, secara yuridis benteng tetap milik Keraton, kemudian secara de facto benteng dikuasai oleh pemerintahan Inggris di bawah pimpinan Jenderal Raffles.
- Tahun 1816-1942, sattus tanah tetap berada pada kepemilikan Keraton, dan secara de facto dipegang oleh pihak Belanda, sampai menyerahnya Belanda di tangan Jepang dan benteng ini mulai dikuasai penuh oleh pihak Jepang, yang ditandai dengan penandatanganan perjanjian Kalijati di Jawa Barat, Maret 1942.
- Tahun 1942-1945, satus tanah tetap milik Keraton, tetapi secara de facto penguasaan berada di tangan Jepang sebagai markas Kempetei atau polisi jepang, gudang mesiu, dan rumah tahanan bagi orang-orang Belanda dan Indo-Belanda serta kaum politisi RI yang menentang Jepang.
- Tahun 1945-1977, status tanah tetap milik Keraton, setelah proklamasi kemerdekaan RI pada tahun 1945, benteng diambil alih oleh instansi militer RI. Dilanjutkan dengan diambil alih kembali oleh pihak Belanda tahun 1948 karena adanya peristiwa Agresi Militer Belanda II, dan akhirnya direbut kembali oleh Indonesia setelah adanya peristiwa Serangan Umum 1 Maret 1949 dan pengelolaan benteng ditangani oleh APRI (Angkatan perang Republik Indonesia).
- Tahun 1977-1992, dalam periode ini, satus pengelolaan benteng diserahkan kembali pada pemerintahan Yogyakarta oleh pihak Hankam, dan pada tanggal 9 Agustus 1980 diadakan perjanjian tentang pemanfaatan bangunan bekas benteng Vredeburg antara Sri Sultan HB IX dengan Mendikbud DR. Daud Jusuf. Hal ini dikuatkan oleh pernyataan dari Mendikbud Prof. Dr. Nugroho Notosusanto tanggal 5 November 1984 bahwa bekas benteng Vredeburg ini akan difungsikan sebagai sebuah museum. Tahun 1985, Sri Sultan HB IX mengijinkan diadakannya perubahan bangunan sesuai dengan kebutuhannya, dan tahun 1987, museum benteng Vredeburg baru dibuka untuk umum. Mengenai status tanah pada periode ini tetap milik Keraton.
- Tahun 1992 sampai sekarang, berdasarkam SK Mendikbud RI Prof. Dr. Fuad Hasan No. 0475/0/1992 tanggal 23 November 1992, secara resmi Museum Bneteng Vredeburg menjadi Museum Khusus Perjuangan Nasional dengan nama Museum Benteng Vredeburg Yoyakarta yang menempati tanah seluas 46.574 m persegi. Kemudian tanggal 5 September 1997, dalam rangka peningkatan fungsionalisasi museum, Museum Benteng Vredeburg Yogyakarta mendapat limpahan untuk mengelola museum Perjuangan Yogyakarta di Brontokusuman Yogyakarta berdasarkan SK Menteri Kebudayaan dan Pariwisata Nomor: KM. 48/OT. 001/MKP/2003 tanggal 5 Desember 2003.