Gereja HKBP terletak di Jl. I Dewa Nyoman Oka No. 22, Yogyakarta. Hari lahir Gereja HKBP ditandai dengan dibaptisnya Jacobus Tampubolon dan Simon Siregar oleh misionaris van Asselt di Sipirok, Tapanuli Selatan pada tanggal 7 Oktober 1861. Bangunan Gereja didirikan pada tahun 1923. Pada awalnya merupakan bangunan Gereformeede Kerk Djogja. Bangunan gereja kemudian difungsikan sebagai tempat dansa dan musik orang – orang Belanda (Muziekenten). Pada masa pendudukan Jepang bangunan ini dipakai sebagai rumah tahanan wanita Belanda (Internerens Camp Belanda). Pada wal tahun 1940-an banyak orang Batak datang ke Pulau Jawa, termasuk di Yogyakarta. Para pemuda datang ke Yogyakarta pada umumnya melanjutkan pendidikan di AMS (Algemene Middelbare School). Pada awalnya orang – orang Batak mengikuti kebaktian di gereja- gereja lain di Yogyakarta (biasanya di Gereja Margamulyo). Pada tanggal 7 April 1946, orang Batak di Yogyakarta untuk pertama kalinya mengadakan kebaktian yang dihadiri sekitar 8 keluarga serta beberapa pemuda dan anak – anak di jalan pakuningratan No.6 Yogyakarta. Kebaktian ini mengatasnamakan HKBP cabang Yogyakarta walaupun secara yuridis formal HKBP di Yogyakarta belum ada. Pertemuan kotbah tanggal 7 April 1946 inilah yang dijadikan hari lahir gereja HKBP Yogyakarta . kebaktian pertama kali dipimpin oleh seorang jemaat yatu J.A Lumbantobing, yang dihadiri antara lain oleh keluarga W. Hutabarat, Aritonang, O. Hutabarat, J.A Lumbantobing dan Siregar. Tempat kebaktian HKBP pertama kali adalah di Jl. Pakuningratan No. 6 Yogyakarta. Dengan meningkatnya jumlah jemaat, maka HKBP Yogyakarta harus mengusahakan tempat kebaktian yang lebih luas. Dari Jl. Pakuningratan No.6 pidah ke SD Ungaran Kotabaru. Pada tanggal 13 Oktober 1946 pindah ke Gereja Margamulya, pindah lagi ke Balai Pertemuan Kristen (BPK) Gondokusuman No. 41 milik Gereja Kristen Jawa Yogyakarta. Pendeta Darmo memberitahukan bahwa di lingkungan BPK masih ada tempat kosong yang dapat digunakan untuk kebaktian. Agar dapat menggunakan tempat tersebut, HKBP harus membayar 10 Gulden seiap bulan untuk biaya perawatan dan pengaturan gedung serta tunjangan bagi pegawai BPK. Dari BPK tempat kebaktian pindah ke Sekolah Menengah Kristen Terban Taman No. 33. Pada tanggal 17 November 1946 tempat kebaktian kembali lagi ke BPK, karena BPK tidak jadi digunakan asrama mahasiswa teologia. Komplek bangunan gereja terdiri dari beberpa bagian, bangunan utama merupakan bangunan lama sebagai tempat ibadah, sisi utara terdapat aula dengan 2 lantai yang merupakan bangunan baru, dan sisi timur serta selatan terdapat bangunan baru yang berfungsi sebagai fasilitas pendukung. Gereja menghadap ke Barat dengan denah berbentuk variasi segi 6 dengan ruang utama berukuran 22×18,6 m. Bangunan ini ditetapkan sebagai cagar budaya dengan Per.Men Budpar RI No. PM.89/PW.007/MKP/2011.