Sebagai imbalannya, Adipati Anom berjanji menyerahkan Madura Barat yang waktu itu dipimpin oleh Tumenggung Yudonegoro kepada Trunojoyo. Di kemudian hari Adipati Anom menyesali perjanjiannya dengan Trunojoyo karena Trunojoyo menolak mengakui Adipati Anom sebagai Sultan Mataram.
Sejarawan Belanda, H.J. De Graaf (1987), menerangkan bahwa Trunojoyo telah mendiami Pulau Madura sekitar tahun 1670-1671. Kemudian De Graaf dalam bukunya “Runtuhnya Istana Mataram” (hal. 60), menuliskan memo Speelman kepada Couper bahwa Raden Trunojoyo meletakkan “landasan pertama pemberontakkannya” di Pamekasan dan “mendapatkan dukungan sepenuhnya dari orang-orang disana”.
Laksamana Speelman merasa yakin bahwa jika Sampang dan Sumenep, yang menurut pendapatnya adalah merupakan daerah-daerah yang bersikap ”baik”, mau menyerah begitu saja, maka Pamekasan yang ”berkeras kepala” itu akan mengikuti pula.
Pada dasarnya penguasaan Trunojoyo atas Madura (Madura Barat khususnya), melalui strategi diplomasi yang jitu menghadapi Tumenggung Yudonegoro. Yang pertama dia membawa hasil perjanjiannya dengan Adipati Anom dan yang kedua dia berhasil meyakinkan Tumenggung bahwa dia adalah pewaris yang sah kekuasaan Madura Barat karena merupakan cucu dari Cakraningrat I. Versi lain tentang penguasaan Trunojoyo atas Madura dapat dibaca pada buku “Bhabad Songennep” karya Raden Werdisastra.
Setelah itu Trunojoyo dengan cepat berhasil membentuk laskar, yang berasal dari rakyat Madura yang tidak menyukai Mataram. Pemberontakan Trunojoyo diawali dengan penculikan Cakraningrat II, yang kemudian diasingkannya ke Lodaya, Kediri. Tahun 1674Trunojoyo berhasil merebut seluruh kekuasaan di Madura, dia memproklamirkan diri sebagai raja merdeka, dan merasa dirinya sejajar dengan penguasa Mataram. Pemberontakan ini diperkirakan mendapat dukungan dari rakyat Madura, karena Cakraningrat II dianggap telah mengabaikan pemerintahan.
Laskar Madura pimpinan Trunojoyo, kemudian juga bekerja sama Karaeng Galesong, pemimpin kelompok pelarian warga Makassar pendukung Sultan Hasanuddin yang telah dikalahkan VOC. Kelompok tersebut berpusat di Demung, Panarukan. Mereka setuju untuk mendukung Trunojoyo memerangi Amangkurat I dan Mataram yang bekerja sama dengan VOC. Trunojoyo bahkan mengawinkan putrinya dengan putra Karaeng Galesong untuk mempererat hubungan mereka. Selain itu, Trunojoyo juga mendapat dukungan dari Panembahan Giri dari Surabaya yang juga tidak menyukai Amangkurat I karena tindakannya terhadap para ulama penentangnya.
Pada bulan September 1676, Trunojoyo dan Madura mulai melakukan ekspansinya ke Mataram. Hingga bulan Oktober 1677, secara luar biasa pasukannya berhasil meringsek maju hingga ke ibukota Kesultanan Mataram di Plered. Secara ringkas penaklukan Trunojoyo disajikan dalam data berikut :
