Setahun setelah diserahkannya Sumenep dan Pamekasan kepada VOC oleh Mataram, para penguasa di wilayah ini secara perlahan mulai terlibat dalam berbagai kerjasama dengan VOC, terutama dalam hal yang menyangkut kegiatan Meliter. Kerjasama ini terjadi pada tahun 1706. Saat itu pasukan VOC, Kartasura, Madura dan Surabaya bersama-sama bersepakat menumpas kekuatan Untung Surapati (Bupati Pasuruan) beserta keturunannya di seluruh Jawa Timur dan Madura. Tak sampai disitu, kerjasama ini kemudian berlanjut pada Perang Suksesi Jawa ke tiga di tahun 1746-1755.
Pada akhir abad ke 17, Batavia mengalami berbagai macam ancaman keamanan, kejadian ini memaksa Gubernur Jenderal VOC Herman Willem Daendels meminta para penguasa diseluruh Pulau Madura untuk mengirimkan ribuan orangnya ke Batavia. Permintaan tersebut dikabulkan, penguasa – penguasa lokal kemudian mengisntruksikan kepada para kepala desa untuk melakukan perekrutan. Orang-orang yang telah dikumpulkan lalu diserahkan kepada pemerintah, lantas dikirim ke Batavia guna menyokong kekuatan tentara kolonial yang minim jumlahnya. Tahun 1811 ribuan pasukan ini juga dilibatkan dalam mempertankan pulau Jawa dari serangan Pasukan Inggris. Mereka disebar di beberapa tempat, antara lain di Batavia dan juga Surabaya.
Meskipun keterlibatan pasukan Madura dalam menjaga keamanan di seluruh kawasan Hindia sempat tertahan pada masa Pemerintahan Inggris, lantas tak membuat segalanya berakhir. Setelah pemerintah Inggris mengembalikan wilayah jajahan kepada pemerintah kerajaan Belanda, kontrak – kontrak baru dengan beberapa penguasa di Pulau Madura kembali dibuat.
Penguasa Sumenep, Pangeran Natanegara (Sultan Sumenep) yang baru beberapa tahun diangkat menggantikan saudaranya, terpaksa memutuskan untuk menandatangani sebuah kontrak yang berisi tentang kesediaannya dalam menyediakan 1080 orang untuk dijadikan pasukan yang bertugas membantu Pemerintah Kolonial di Surabaya. Pasca ditandanganinya kontrak baru tersebut, pasukan Sumenep semakin aktif diperbantukan dalam berbagai ekspedisi meliter, mulai dari ekspedisi ke Bone tahun 1824-1825 hingga perang terbesar sepanjang sejarah, perang Jawa tahun 1825-1930.
Selepas perang usai, melalui surat keputusan tanggal 12 Februari 1831, Gubernur Jendral JG van den Bosch meminta Residen Surabaya untuk segera membentuk organisasi meliter yang permanen di seluruh wilayah Kerajaan di Pulau Madura. Residen Surabaya, H. J. Domis secara khusus ditunjuk mewakili pemerintah untuk menyampaikan hal ini kepada para penguasa di Madura. Ia ditugaskan untuk mempersiapkan segala macam hal menyangkut pembentukan kesatuan ini. Beberapa bulan setelahnya, pada tanggal 17 Agustus 1831 bersama – sama dengan Sultan Madura, Panembahan Pamekasan dan juga Sultan Sumenep kesatuan ini diresmikan dengan nama “Korps Barisan”.
Korps meliter ini dibina langsung oleh para perwira Eropa. Masing – masing di wilayah Kerajaan terdapat satu batalyon. Satu batalyon korps Barisan dibagi kedalam lima kompi, masing –masing terdiri dari kompi pasukan kavaleri, pasukan arteliri, pasukan infanteri dan pasukan pikenier sehingga kesatuan ini lebih mirip sebuah pasukan gabungan. Di masa awal pembentukannya, Korps Barisan dipimpin langsung oleh penguasa setempat dengan pangkat tertinggi yakni Mayor Jendral sedangkan para putra-putranya dianugrahi pangkat Letnan Kolonel. Seluruh pembiayaaan pasukan ini ditanggung oleh kedua belah pihak, antara lain kerajaan dan juga pemerintah kolonial.
Korps Barisan mulai mengalami beberapa perubahan secara mencolok pada saat dihapuskannya pemerintahan kerajaan di seluruh Madura. Pertama–tama yang mengalami perombakan adalah Korps Barisan Pamekasan pada tahun 1858 lalu kemudian Korps Barisan Sumenep tahun 1882 dan terakhir Korps Barisan Bangkalan pada tahun 1885.
Perubahan struktur dan administrasi berakibat pada pemangkasan beberapa hal. Jika semula kendali pasukan berada dibawah pimpinan seorang setempat (Sultan atau Panembahan), kali ini semua kesatuan berada dalam kendali Pemerintah Kolonial. Tak hanya itu, kompi – kompi pasukan kavaleri dan artileri dihapuskan, pun juga dengan pasukan pikenier mengalami nasib yang sama. Sejak berada dalam kendali pemerintah Kolonial, Barisan bukan lagi menjadi semacam pasukan gabungan melainkan sebagai pasukan infanteri mirip angkatan darat Hindia – Belanda (KNIL).
 |
| Infografis keterlibatan Korps Barisan Sumenep dalam berbagai pertempuran di berbagai wilayah Hindia-Belanda |
