Di dalam perkembangannya, Kantor Pelayanan Perbendaharaan Negara (KPPN) Malang memiliki sejarah yang cukup panjang dan telah banyak mengalami perubahan, baik 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). 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 Malang berubah menjadi Kantor Pelayanan Perbendaharaan Negara (KPPN) Malang 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 Malang yang menjadi Tipe A1.
Dan pada tanggal 2 Oktober 2012 melalui softlaunching KPPN Percontohan tahap VI, KPPN Malang ditetapkan menjadi KPPN Percontohan dengan Keputusan Dirjen Perbendaharaan No. KEP-163/PB/2012.
Sementara mengenai tempat kedudukan, sebelum tahun 1947 KPPN Malang yang masih bernama KKN berada di Bank Tunggal, Jalan Talun Lor Malang (sekarang Jalan Arif Rahman Hakim Malang). Pada saat terjadi Agresi Belanda tahun 1947, untuk menyelamatkan dokumen administrasi keuangan, KKN dipindahkan ke Turen.
Setelah penyerahan kedaulatan oleh Belanda kepada pemerintah Republik Indonesia tahun 1950, KKN dipindah kembali dari Turen ke Bank Tumapel di Jalan Talun Lor Malang.Dengan semakin meningkatnya beban pekerjaan, tahun 1952 dipindah ke Jalan Merdeka Selatan Nomor 1- 2 Malang hingga saat ini.
