Kereta api Brawijaya diluncurkan pada 10 Maret 2021 di Stasiun Gambir untuk membantu tugas KA yang beroperasi sebelumnya seperti kereta api Jayabaya di koridor Jakarta–Surabaya–Malang, Majapahit, Matarmaja di koridor Jakarta–Semarang–Malang dari lintas utara, dan Gajayana di koridor Jakarta–Yogyakarta–Malang dari lintas tengah Pulau Jawa yang menjadi rute utama dari koridor tersebut.
Perjalanan kereta api ini menempuh jarak 881 km dalam waktu sekitar 12 jam 55 menit[1] dan kereta api Brawijaya menambah pemberhentian di Stasiun Cikarang mulai 1 Maret 2022.
Per pertengahan Mei 2023 sebelum dimulai dengan pemberlakuan grafik perjalanan kereta api (Gapeka 2023), kereta api Brawijaya ini diambil alih kepemilikan operasional ke Daerah Operasi VIII Surabaya dari Daerah Operasi I Jakarta beserta rangkaian kereta pun dimutasi ke Depo Kereta Malang, yang disebabkan dua kereta baru yang akan datang di Gapeka 2023, yakni kereta api Argo Semeru dan Pandalungan yang sama-sama kepemilikan operasional ke Daerah Operasi I Jakarta.
Mulai 3 Mei 2024, Kereta api Brawijaya sudah menggunakan rangkaian kereta eksekutif baja ringan new image yang merupakan lungsuran dari Kereta api Sembrani, yang kini Kereta api Sembrani sudah mendapatkan rangkaian baja nirkarat (stainless steel) dari lungsuran Kereta api Argo Bromo Anggrek.
Kereta api Brawijaya nomor 58 menuju Malang tertemper truk muatan pasir di perlintasan tanpa sebidang di Kecamatan Gampengrejo, Kabupaten Kediri, Jawa Timur; tepatnya di petak antara Stasiun Papar dan Kediri di jalur percabangan Kertosono–Malang pada hari Minggu dini hari jam 03:00 WIB. Meskipun tidak ada korban jiwa atau luka pada kejadian tersebut, lokomotif tersangkut oleh temperan truk saat melintas yang mengakibatkan kerusakan. Imbas dari kejadian tersebut, lalu lintas kereta api di petak antara Kertosono dan Kediri mengalami gangguan sehingga KA Gajayana nomor 56 dari Jakarta Gambir serta Malabar nomor 122 dari Bandung harus dialihkan melalui jalur utama selatan–tengah Jawa di koridor Kertosono–Surabaya dan jalur percabangan Tarik–Sidoarjo.[4]
Hanya berisi layanan kereta api yang dioperasikan oleh induk perusahaan. Untuk layanan yang dioperasikan oleh anak perusahaan, lihat Templat:KAI Commuter untuk layanan KAI Commuter, Templat:KAI Bandara untuk layanan KAI Bandara dan Templat:KCIC untuk layanan KCIC/Whoosh