Sejarah KPPN Bondowoso dimulai dengan dibentuknya Kantor Kas Negara (KKN) Bondowoso pada tahun 1960. Selanjutnya, pada tahun 1975, dibentuk Kantor Perbendaharaan Negara (KPN) Bondowoso. KPN adalah instansi vertikal di bawah Direktorat Jenderal Anggaran yang mempunyai tugas dan fungsi untuk melaksanakan pembayaran gaji pegawai negeri sipil dan pembayaran pensiun pegawai negeri sipil dalam wilayah karesidenan Besuki dan sekitarnya (meliputi daerah Besuki, Situbondo, Bondowoso, Jember, dan Banyuwangi.
Dalam rangka menyesuaikan dengan perkembangan organisasi, pada tanggal 1 April 1990 KPN Bondowoso digabungkan dengan Kantor Kas Negara (KKN). Dengan penggabungan kedua kantor tersebut maka nama KPN dan KKN berubah menjadi Kantor Perbendaharaan dan Kas Negara (KPKN) Bondowoso.
Pada tahun 1997, sebagai tindak lanjut dari Surat Keputusan Menteri Keuangan Republik Indonesia tanggal 2 Januari 1997 Nomor : 1/KMK.01/1997 tentang Organisasi dan Tata Kerja Direktorat Jenderal Anggaran dan berdasarkan Surat Edaran Direktur Jenderal Anggaran tanggal 22 Juli 1997 Nomor : SE-90/A/61/0797, terhitung mulai tanggal 30 September 1997 KPKN Bondowoso resmi ditutup. Latar belakang penutupan kantor tersebut adalah dalam rangka meningkatkan efisiensi dan efektifitas pelaksanaan tugas pokok Direktorat Jenderal Anggaran di bidang Anggaran Pendapatan dan Belanja Negara sesuai kebijaksanaan yang ditetapkan oleh Menteri Keuangan dan Peraturan Perundang-undangan yang berlaku.
Dalam perkembangannya, pada tahun 2001 berdasarkan Keputusan Menteri Keuangan Republik Indonesia tanggal 23 Juli 2001 Nomor : 442/KMK.01/2001 tentang Organisasi dan Tata Kerja Kantor Wilayah Direktorat Jenderal Anggaran, Kantor Perbendaharaan dan Kas Negara, dan Kantor Verifikasi Pelaksanaan Anggaran serta Keputusan Menteri Keuangan Republik Indonesia tanggal 2 Agustus 2001 Nomor : Kep-34/A/2001 mengenai Penetapan Kanwil DJA, KPKN dan Kantor Verifikasi Pelaksanaan Anggaran, KPKN Bondowoso secara resmi dibuka kembali.
Perubahan nomenklatur terakhir terjadi pada tahun 2005, seiring dengan terjadinya reorganisasi di Kementerian Keuangan (saat itu masih bernama Departemen Keuangan), yaitu dengan terbentuknya Direktorat Jenderal Perbendaharaan. Perubahan mendasar dari KPKN menjadi KPPN (Kantor Pelayanan Perbendaharaan Negara) ini juga sejalan dengan amanat Undang-Undang nomor 17 tahun 2003 tentang Keuangan Negara serta Undang-Undang nomor 1 tahun 2004 tentang Perbendaharaan Negara. Seusai dengan ketentuan dalam kedua undang-undang diatas, maka kewenangan administratif (ordonnateur) berada pada kementerian / lembaga sedangkan fungsi kebendaharaan (comptable) berada pada Menteri Keuangan yang dalam hal ini dijalankan oleh KPPN selaku Kuasa Bendahara Umum Negara (Kuasa BUN) di daerah.
Dalam rangka mewujudkan tata kelola pemerintahan yang baik (good governance), pimpinan Direktorat Jenderal Perbendaharaan bertekad untuk membentuk suatu kantor pelayanan yang dapat memberikan layanan yang cepat, tepat, akurat, transparan, dan tanpa biaya. Berdasar hal inilah, maka KPPN Bondowoso menjalankan perubahan terus menerus guna meningkatkan kepuasan publik atas layanan perbendaharaan yang diberikan, dengan cara meningkatkan kapasitas SDM, meningkatkan kualitas sarana dan prasarana, serta memberikan bimbingan perbendaharaan kepada satuan kerja dan pemangku kepentingan. Mulai tahun 2010, KPPN Bondowoso telah menjalankan Standard Operating Prosedures (SOP) KPPN Percontohan.
Saat ini wilayah kerja KPPN Bondowoso meliputi 3 kabupaten dan 1 kota, yaitu Kabupaten Bondowoso, Kabupaten Situbondo, Kabupaten Probolinggo, dan Kota Probolinggo.
