Pertempuran Gegodog

Sebelum pemberontakan, ningrat Madura Trunajaya hidup dalam pengasingan di Mataram dan memiliki hubungan dekat dengan putra mahkota Mataram (kemudian dikenal sebagai Pangeran Adipati Anom, kelak Amangkurat II). Ayah mertua Trunajaya dan seorang ningrat terkemuka, Raden Kajoran telah memperkenalkannya kepada putra mahkota pada tahun 1670. Keduanya memiliki dendam terhadap Raja Amangkurat I, putra mahkota atas eksekusi Pangeran Pekik, kakek sang pangeran dari pihak ibu, dan Trunajaya atas pengasingannya dan eksekusi ayahnya. Mereka berdua membina persahabatan, sebagian karena faktor ketidaksukaan bersama ini. Pada tahun 1670 atau 1671, Trunajaya meninggalkan Mataram menuju kampung halamannya Madura dan menjadi penguasanya. Dia memanfaatkan dukungan putra mahkota (serta nama keluarganya sendiri) untuk memperoleh pengikut yang memungkinkan dia untuk merebut penguasaan pulau.
Pemberontakan Trunajaya mulai pada tahun 1674 ketika pasukan Trunajaya menyerang kota-kota di bawah penguasaan Mataram. Pada tahun 1676, pasukan pemberontak berjumlah 9.000 menyerbu Jawa Timur dari basis mereka di Madura, dan merebut Surabaya —kota utama di Jawa Timur— tidak lama sesudahnya. Pasukan tersebut terdiri dari orang Jawa Timur, Madura, dan Makassar dan dipimpin oleh Trunajaya dan sekutu Makassar-nya, Karaeng Galesong.