SMA Negeri 4 Yogyakarta awalnya bernama SMA Perdjoangan.
Pada mulanya sekolah ini disediakan untuk pelajar yang telah menunaikan kewajibannya bertempur melawan penjajah dan berbakti kepada negara sebagai Tentara Pelajar Brigade 17 yang memobilisasi pelajar.
Pada tahun 1952 SMA Perdjoangan dijadikan SMA Negeri dengan nama SMA bagian B nomor II Negeri. SMA ini menggunakan gedung SMAN 3 Yogyakarta di Jl. Yos Sudarso No. 7. Pada perkembangan selanjutnya terjadi perubahan nama menjadi SMA 4B dan sampai sekarang terkenal dengan nama SMA 4Bhe. Pada tahun 1963 nama SMA 4Bhe berubah lagi menjadi SMA Negeri IV. Nama ini tetap digunakan sampai kepindahannya ke gedung sekolah milik sendiri yang terletak di Jalan Magelang Karangwaru Lor Yogyakarta.
Sejak menempati gedung baru nama SMA Negeri IV mengalami perubahan lagi menjadi SMA Negeri 4 Yogyakarta sampai saat ini.
Seiring pergantian nama dan perpindahan gedung sekolah SMAN 4 Yogyakarta, perpustakaan mengalami perpindahan tempat selama 4 kali. gedung perpustakaan pertama berada di depan( sekarang menjadi ruang guru) kemudian perpindahan kedua di ruangan sebelah timur UKS kemudian pindah ke bangunan belakang dekat kantin sekolah, tetapi karena letaknya yang tidak strategis dan hampir tidak pernah dikunjungi akhirnya perpustakaan dipindahkan ke ruangan semula yaitu sebelah timur ruang UKS dengan memperluas ruangan hingga saat ini.