Le Nagarakertagama, poème épique écrit en 1365 sous le règne du roi Hayam Wuruk (1350-89) de Majapahit, dresse une liste des "contrées tributaires" de Majapahit, qui, outre Madura, Sunda et Bali, va de Pahang en Malaisie à "Gurun" dans les Moluques, en passant par Malayu à Sumatra et "Bakulapura" à Bornéo.
Dans sa Suma Oriental, Tomé Pires, un apothicaire portugais qui de 1512 à 1515 a vécu à Malacca, dont le souverain était musulman, écrit que Madura n'est pas encore musulmane. D'après la tradition, les Madurais auraient commencé à se convertir à l'islam en 1528, c'est-à-dire juste après la prise de Kalapa, le port du royaume hindouiste sundanais de Pajajaran en 1527 par un prince musulman de Banten.
Madura est conquise en 1624 par les troupes du Sultan Agung du royaume de Mataram à Java. Agung impose à l'île, jusqu'alors divisée en plusieurs petites principautés, une lignée qui prendra en 1678 le nom de Tjakraningrat.
En 1671, le prince Trunajaya, avec l'appui de conspirateurs javanais qui projettent de s'emparer du trône de Mataram, prend le pouvoir à Madura. Allié à des soldats de Makassar qui avaient fui Célèbes après la défaite du sultanat de Gowa devant les Hollandais, Trunajaya entreprend de conquérir Mataram, se prétendant descendre des rois de Majapahit. En 1677, il prend la capitale de Mataram, qu'il pille, mais il finira par être défait par les Javanais alliés aux Hollandais.
