KPPN Madiun memiliki sejarah cukup panjang, mengalami perubahan nama maupun struktur organisasi. Pada masa penjajahan Belanda bernama CKC (Central Kantoor voor de Comptabiliteit) dan Slank Kas. Setelah Proklamasi Kemerdekaan RI, antara tahun 1945-1947 Kas Negara dipegang langsung oleh bangsa Indonesia sendiri dan saat itu nama CKC dan Slank Kas diindonesiakan, yaitu CKC menjadi KPPN (Kantor Pusat Perbendaharaan Negara sedangkan Slank Kas menjadi KKN (Kantor Kas Negara) yang pada akhirnya ditetapkan saat itu juga bahwa KPPN dan KKN tersebar di seluruh wilayah Indonesia.
Pada tahun 1951, pemerintah Indonesia menetapkan bahwa di tiap-tiap Karisedenan terdapat kas negara, kemudian pada tahun 1968 nama KPPN dan KKN digabung menjadi KBN (Kantor Bendahara Negara). Pada tahun 1974 KBN mengalami perubahan struktur organisasi menjadi 3 instansi, yaitu KPN (Kantor Pelayanan Negara) dan KKN (Kantor Kas Negara) dan Satuan Kerja dan berdasarkan Surat Keputusan Menteri Keuangan tanggal 3 Maret 1983 Nomor 205/KMK.01/1983 tentang Organisasi dan Tata Kerja Instansi Vertikal Direktorat Jenderal Anggaran, KBN dipecah lagi menjadi Kantor Perbendaharaan Negara (KPN) dan Kantor Kas Negara (KKN). Seiring dengan perkembangan jaman yang mengacu pada pola penyederhanaan organisasi maka berdasarkan Surat Keputusan Menteri Keuangan Nomor 645/KMK.01/1989 tanggal 12 Juni 1989 dan Surat Edaran Direktur Jenderal Anggaran nomor : SE-1077/A/1989 tanggal 14 September 1989 tentang Organisasi dan Tata Kerja Instansi Vertikal Direktorat Jenderal Anggaran, sejak tanggal 1 April 1990 KPN dan KKN digabung menjadi KPKN (Kantor Perbendaharaan dan Kas Negara). Berkenaan dengan tempat kedudukan KPPN Madiun pada saat masih bernama Kantor Bendahara Negara (KBN) berlokasi di Jalan Pahlawan Madiun. Dikarenakan dilanda bencana banjir besar kantor berpindah ke Jalan Salak Nomor 52 Madiun yang gedungnya diresmikan oleh Direktur Jenderal Anggaran Mayjen TNI Piet Harjono pada tanggal 30 Juni 1975.
Dasar pertimbangan dari penggabungan ini antara lain adalah dalam rangka efisiensi dan mengurangi jalur birokrasi dalam pelayanan kepada masyarakat yang semula dilakukan oleh dua kantor yang berbeda menjadi hanya satu kantor, yang kita kenal dengan istilah SAMSAT (Sistem Administrasi Manunggal Satu Atap). Pertimbangan lain penggabungan institusi ini adalah berkurangnya beban kerja Kantor Perbendaharaan Negara (KPN) yang disebabkan oleh dialihkannya pembayaran pensiun ke PT. Taspen dan Perum Asabri dan dialihkannya pembayaran secara tunai pada Kantor Kas Negara (KKN) menjadi pembayaran secara giral pada Bank-Bank Pemerintah yang ditunjuk.
Hal ini diiringi pula dengan perubahan mekanisme pembayaran dalam pelaksanaan APBN diantaranya giralisasi dan perubahan sistem UUDP menjadi UYHD yang semakin mempermudah masyarakat dalam rangka pengelolaan dana APBN. Begitu pula halnya perubahan KPKN yang cukup mendasar, diantaranya peran selaku Ordonatur yang memiliki kewenangan di bidang ordonansering yaitu melakukan pengujian atas permintaan pembayaran oleh instansi/satuan kerja atau pihak-pihak yang memiliki hak tagihan pada negara beralih kepada pengguna anggaran/kuasa pengguna anggaran, dalam hal ini adalah pimpinan satuan kerja/instansi. Sementara KPKN melaksanakan fungsi sebagai Bendahara Umum Negara (Comptabel). Perubahan ini diharapkan dapat memberikan pelayanan yang lebih baik kepada masyarakat secara cepat, tepat dan sistematis.
Selanjutnya pada tahun 2004, untuk lebih meningkatkan pelayanan publik secara transparan dan akuntabel serta sebagai wujud dari pelaksanaan reformasi birokrasi maka berdasarkan Surat Keputusan Menteri Keuangan Nomor 302/KMK.01/2004 dan 203/KMK.01/2004 KPKN Madiun berubah menjadi Kantor Pelayanan Perbendaharaan Negara (KPPN) Madiun tipe A. Dalam rangka meningkatkan kinerja Kantor Vertikal di lingkungan Direktorat Jenderal Perbendaharaan, serta penyempurnaan terhadap organisasi dan tata kerja Kantor Wilayah dan Kantor Pelayanan Perbendaharaan Negara maka sesuai dengan Peraturan Menteri Keuangan nomor 101/PMK.01/2008 Kantor Pelayanan Perbendaharaan Negara Tipa A mengalami perubahan tipe termasuk KPPN Madiun yang menjadi Tipe A1. Pada tanggal 2 Oktober 2012 melalui softlaunching KPPN Percontohan tahap VI, KPPN Madiun ditetapkan menjadi KPPN Percontohan dengan Keputusan Dirjen Perbendaharaan No. KEP-163/PB/2012.