Pada grafik perjalanan kereta api (Gapeka) 2019, jenama Madiun Jaya kembali digunakan oleh KAI untuk layanan kereta api aglomerasi fakultatif kelas campuran eksekutif dan bisnis, yakni KA Madiun Jaya dengan relasi Madiun–Surabaya Pasarturi–Kandangan. Layanan KA Madiun Jaya (Madiun–Kandangan) dihapus sejak berlakunya Gapeka 2023.
Kereta api ini mulai beroperasi pada 1 Februari 2025, seiring berlakunya Gapeka tahun 2025. Dengan waktu tempuh rata-rata 8 jam 59 menit, menjadikannya layanan kelas campuran dengan waktu tempuh tercepat pada rute Pasar Senen–Yogyakarta–Madiun.
Kereta eksekutif retrofit tahun 2025 produksi Balai Yasa Manggarai saat uji coba
Pada awal pengoperasian, rangkaian kereta api Madiun Jaya terdiri dari satu kereta pembangkit, enam kereta ekonomi baja nirkarat generasi pertama, satu kereta makan, dan dua kereta eksekutif baja ringan dengan ciri khas kaca lebar. Namun, mulai 21 Maret 2025, dua kereta eksekutif tersebut diganti dengan dua kereta eksekutif retrofit tahun 2025 yang merupakan produksi Balai Yasa Manggarai. Dua unit kereta eksekutif tersebut merupakan retrofit dari kereta eksekutif buatan tahun 2002 dan 2009, serta menggunakan kursi yang serupa dengan kereta eksekutif baja nirkarat generasi dua. Madiun Jaya menjadi kereta api pertama yang menggunakan kereta eksekutif retrofit tersebut.
Adapun menurut Gapeka 2025, rangkaian kereta api Madiun Jaya dialokasikan oleh Depo Kereta Jakarta Kota dan beristirahat di Depo Kereta Cipinang. Kereta ekonomi yang digunakan oleh kereta api Madiun Jaya merupakan bekas dari kereta api Kutojaya Utara reguler yang sudah tidak beroperasi sejak berlakunya Gapeka 2025.
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
.svg)
