kereta api gajayana diresmikan pengoperasiannya pada tanggal 28 oktober 1999.
sempat dirangkaikan dengan kelas bisnis pada awal pengoperasiannya.
nama gajayana berasal dari seorang raja dari kerajaan kanjuruhan yang bernama sang liswa (anak dari dewa shima) dan terkenal dengan gelar gajayana yang sangat dicintai oleh para brahmana dan rakyatnya karena membawa ketenteraman di seluruh negeri.
kerajaan kanjuruhan ini berpusat di wilayah dinoyo, lowokwaru, kota malang, jawa timur.
kereta ini beroperasi dengan kelas eksekutif dan bisnis pada awalnya, karena saat itu (1999) ka turangga baru mendapat rangkaian baru dari inka, maka kereta kelas bisnis dari turangga diberikan ke ka gajayana.
pada tahun 2001, karena ka gajayana mendapat rangkaian baru dari inka, maka kereta ini menjadi rangkaian khusus eksekutif.
sejak oktober 2008, rangkaian gajayana diubah dari rangkaian buatan 2001 menjadi menggunakan kereta eksekutif (k1) satwa retrofit (kaca lebar) dari pt inka. kereta ini adalah kereta eksekutif lama yang diretrofit menjadi baru.
pascalebaran 2009, rangkaian kereta api gajayana diubah menjadi kereta berkaca pesawat (keluaran 2009) sampai dengan sekarang dan kereta gajayana satwa kini digunakan untuk ka bangunkarta eksekutif sejak 5 desember 2009.
rangkaian baru ini diresmikan oleh presiden republik indonesia, susilo bambang yudhoyono, di stasiun jakarta kota.
kemudian pada tahun 2016, rangkaian ka gajayana sempat menggunakan rangkaian terbaru dari pt inka menggunakan bogie k10 yang mirip rangkaian ka argo bromo anggrek, sebelum rangkaian baru itu dialokasikan untuk kereta lain.
perjalanan sejauh 907 km ditempuh dalam waktu sekitar 14,5-15,5 jam dan hanya berhenti di stasiun malang, malang kotalama (hanya ka 42, ke arah timur), kepanjen, wlingi, blitar, tulungagung, kediri, rangkaian kereta gajayana terdiri dari 6 sampai 8 kereta eksekutif argo (k1), 1 kereta makan motif batik (m1), 1 kereta pembangkit listrik (p), dan 1 kereta bagasi (b).
fasilitas di ka ini yang tersedia: toilet, pintu otomatis, 2 tv (depan-belakang), ac central, reclining seat, sandaran kaki, lampu baca, meja makan per kursi, stopkontak per kursi, dan rak bagasi.
karena merupakan kereta lintas malam, tersedia pula bantal dan selimut di tiap kursi.
pada pagi harinya, rangkaian yang berada di jakarta difungsikan sebagai kereta api argo parahyangan tambahan, dari jakarta dan tujuan ke bandung.
tarif kereta api ini adalah antara rp 265.000,00 - rp 570.000,00, bergantung pada jarak yang ditempuh penumpang, subkelas/posisi tempat duduk dalam rangkaian kereta, serta hari-hari tertentu seperti akhir pekan dan libur nasional.
selain itu, berlaku pula tarif khusus yang hanya dapat dipesan di loket stasiun mulai dua jam sebelum keberangkatan pada stasiun-stasiun yang berada di dalam rute berikut.
malang - madiun maupun sebaliknya: rp 100.000,00
kediri - yogyakarta maupun sebaliknya: rp 150.000,00
madiun - yogyakarta maupun sebaliknya: rp 80.000,00
cirebon - jakarta maupun sebaliknya: rp 150.000,00.
berikut ini adalah jadwal perjalanan ka gajayana per 1 april 2015 (berdasarkan gapeka 2015).
per 1 desember 2015, ka ini juga berhenti di kertosono.
ka 41 gajayana (malang - gambir)
ka 42 gajayana (gambir - malang)
kereta api gajayana menabrak kendaraan angkutan rakitan ledok di perlintasan tanpa palang pintu di desa kromasan, ngunut, tulungagung, dekat stasiun ngunut.
menurut perkataan kepala stasiun ngunut, 19 mei 2010, kejadian terjadi sekitar pukul 07.15 wib dan tidak ada korban tewas dalam musibah ini.
meskipun tidak berpalang dan tidak dijaga, perlintasan tersebut menjadi andalan bagi para sopir ledok tersebut untuk mengangkut sayuran.
tempo.co: kereta eksekutif gajayana tabrak ledok
pada tanggal 4 januari 2011, empat rangkaian gerbong eksekutif kereta api gajayana yang sedang parkir di stasiun malang tiba-tiba mundur dan menabrak empat rumah.
satu orang balita tewas dalam kejadian tersebut.
kompas: berita foto: gajayana tabrak rumah
pada 27 agustus 2011, kereta api gajayana yang dimasinisi oleh yodian wiliarso dan diasisteni oleh bambang suradi dibajak oleh tiga orang yang masuk kabin masinis lokomotif.
sebanyak tiga pembajak masuk lokomotif dan mengarahkan kereta api tersebut ke stasiun pasar senen.
mulanya, kereta ini tertahan sinyal masuk di stasiun jatibarang, kemudian saat di stasiun telagasari beberapa orang menghadang kereta api dan satu orang masuk lokomotif.
kereta sempat berhenti di stasiun haurgeulis untuk menurunkan penumpang gelap di lokomotif.
lalu sang masinis memberitakan kepada pusat kendali (pk) cirebon agar diberikan sinyal aspek hijau dan melaju tanpa henti di sepanjang jalur rel hingga gambir.
selama pembajakan berlangsung, masinis sempat kehilangan kontak.
masinis kemudian memberitahu pk baru pada pukul 09.08 bahwa masinis tersebut disandera dan meminta agar pk mengarahkan kereta itu langsung ke gambir.
ka gajayana lantas mencoba berhenti di jatinegara namun gagal dan diarahkan ke stasiun pasar senen.
pada pukul 09.35 gajayana masuk jalur 4 dan berhenti dengan rem darurat oleh petugas teknisi, dan dihadang aparat brimob yang sudah siaga di bibir peron.
kompas: inilah kronologi kasus pembajakan ka gajayana
pada tanggal 18 maret 2015, sekitar pukul 14.00, kereta api gajayana berhenti luar biasa karena dihadang oleh dua orang petani yang mengetahui bahwa ada kerusakan rel.
posisinya berada di km 53 di daerah malang.
tribunnews surabaya: 2 petani hentikan ka gajayana, ratusan penumpang selamat
seorang ayah bersama anaknya, nekat menabrakkan diri ke kereta api gajayana di dekat stasiun purwosari pada tanggal 20 maret 2015 malam itu, dikarenakan bercerai dengan istrinya.
solopos: bunuh diri solo: bopong putrinya, ayah tabrakkan diri ke kereta api di stasiun purwosari suaranews: ayah koplak!
galau ajak anak bunuh diri
pada tanggal 12 april 2015, dua orang perempuan yang mengendarai sepeda motor tewas ditabrak kereta api gajayana di perlintasan tanpa palang pintu di desa jambean, kras, kediri.
tribun: dua perempuan berboncengan motor tersambar gajayana
berkas:sbl2.jpg|kereta api gajayana masuk [[stasiun sumbergempol]]berkas:p1040254.jpg|kereta api gajayana langsung [[stasiun sumberpucung]].