Setelah dapat menguasai Madura, Belanda lewat vas der Plas selaku pemimpin Recamba Jawa Timur membujuk Cakraningrat dalam upayanya menjalin kerja sama untuk membentuk Negara Madura. Kerja sama ini ternyata disambut oleh Cakraningrat, sehingga akhirnya Madura dapat dibentuk menjadi sebuah negara, dan Cakraningrat diangkat menjadi Wali Negaranya
Keberhasilan membentuk Negara Madura, tidak terlepas dari kelihaian Belanda dalam mendekati selain para. pemimpin formal seperti Cakraningrat, juga pendekatan terhadap para pemirnpin non-formal yang dalam masyarakat Madura mempunyai pengaruh yang amat besar, yaitu Alim Ulama atau Kyai. Disamping itu juga terlihat uanya sambutan sebagian masyarakat terhadap pembentukan negara ini yang ditunjukkan lewat hasil dari suatu plebisit
Negara Madura yang telah berhasil dibentuk, sebagai layaknya sebuah negara, negara tersebut terdapat pula organ-organ pemerintahan, seperti DPR, Departemen-Departemen, dan organ-organ lainnya Sedangkan sebagai landasan hukumnya, negara ini juga memiliki sebuah “Peraturan Ketatanegaraan” yang berfungsi sebagai Undang-Undang Dasarnya
Akan tetapi dalam realitasnya, negara bikinan Belanda ini ternyata hanya bertahan relatif singkat. Golongan-golongan pro-Republik, seperti yang tergabung dalam Batalyon 635 Jokotole dan Pemerintahan Sipil Bayangan di Pengasingan Jawa, Gerakan Perjuangan Madura di Yogyakarta, dan Organisasi-Organisasi Gerakan Bawah Tanah, dengan merangkul masyarakat luas secara terus-menerus melakukan berbagai upaya untuk membubarkan Negara Madura tersebut.
