Непрерывной борьбе с мятежами сопутствовала атмосфера подозрительности и страха, в которой зрели новые, в известном смысле более опасные, ростки столичного мятежа. Он был организован в 1319 г. неким Кути, начальником полицейских сил, из числа старых друзей Кертараджасы. Кути, возможно, также попал в число обвиняемых в измене, но не покинул Маджапахита, а вместе с пятью-шестью привилегированными офицерами организовал заговор, целью которого было свержение Джаянагары. Ему удалось даже на некоторое время захватить столицу. Однако сам махараджа с группой телохранителей ускользнул из рук заговорщиков, верные ему люди проникли в город, совершили контрпереворот и казнили Кути. Решающую роль в этом сыграл начальник личной охраны государя Гаджа Мада, который и стал затем, при следующих правителях Маджапахита, мапатихом, а фактически — первым лицом в государстве, подлинным «строителем» империи.
К началу 20-х годов XIV в., когда полоса мятежей, угрожавших господству объявленной Кертараджасой династии Раджасы, кончилась, в стране наступил период внутренней стабильности, экономического и политического подъема. Смерть тяжело больного махараджи Джаянагары под скальпелем своего лейбмедика в 1328 г. мало что меняла в этой картине, хотя местные хроники и утверждают не без основания, что все это было инспирировано Гаджа Мадой, который к тому времени стал патихом Кедири.
НОВЫЕ ФАКТОРЫ В ПОЛИТИКЕ ГОСУДАРСТВ РЕГИОНА. РАСПРОСТРАНЕНИЕ ИСЛАМАВ первой четверти XIV в. внешнеполитическая ситуация, по-видимому, не очень благоприятствовала Маджапахиту. Это определялось рядом причин. С конца XIII в. на северо-западных рубежах малайскоиндонезийских владений появилась новая мощная угроза: тайские королевства, и прежде всего наиболее сильное из них — Сукотаи. При короле Рама Камхенге (1275—1317) таи сокрушили монские княжества в долине реки Менам и нанесли ряд поражений кхмерскому Ангкорскому государству; уже в 80-х гг. XIII в. они приступили к захватам на Малаккском полуострове, где были старые малайские портовые города; они установили протекторат над Южной Бирмой и пытались овладеть Тямпой. К 90-м гг. столетия тайская держава подчинила неч только многие монкхмерские территории, но и значительную часть бывших владений Шривиджаи на Малаккском полуострове. Рама Камхенг вел умелую дипломатическую игру с монгольской династией Юаней в Китае. Важнейшим направлением его экспансии было южное, в сторону внешнеторговых форпостов в зоне Малаккского пролива. Не только малайские полуостровные территории, но и восточносуматранская область Мелаю стали объектами экспансии Сукотаи. Ни окончательно ослабевшая Шривиджая, ни яванское государство, которое еще недавно держало в Мелаю свои войска, но теперь было приковано к своим внутренним делам, не могли тогда эффективно бороться с этим противником.
После смерти Рама Камхенга в 1318 г. и ослабления Сукотаи северомалаккские прибрежные княжества восстановили свою независимость, а на крайнем юге Малайи усилился молодой торговый центр, княжество Тумасик (Сингапур), основанное в 1299 г. Практически до 30—40-х гг. XIV столетия (до походов, организованных Гаджа Мадой) Маджапахит не мог реально претендовать на овладение малайскими областями Западной Нусантары. Но в этот сравнительно короткий период наблюдается не только оживление самостоятельной политики индуистско-буддийских государственных образований, временно освободившихся от давления с севера (Сиам) и с юго-востока (Маджапахит), но и появление совершенно нового политико-идеологического фактора в лице первых исламизированных режимов.
Как предположительно следует из ссылок на Нусантару в арабомусульманских источниках, торговые общины мусульман стали появляться здесь в раннем средневековье, т. е. в VIII—X вв. Логично также считать, что раньше и чаще других с исламизированной культурой Ближнего Востока контактировали территории, прилегающие к зоне Малаккского пролива. В ряде портовых центров на пути в Китай длительное время существовали группы заморских купцов-мусульман, а в конце XIII в., когда в Гуджарате и ряде других областей Индии, издавна связанных торговлей с Западной Индонезией, стал утверждаться ислам, регулярная проповедь мусульманской доктрины и обращение в новую веру малайских правителей явились неизбежным следствием экономических и культурно-политических связей. Однако не следует забывать, что процесс исламизации Нусантары, начало которого можно отнести именно к концу XIII — началу XIV вв., первоначально наиболее активно происходил там, где древняя классовая религиозная система, оформленная индуистскими и буддийскими культами, еще не утвердилась достаточно прочно либо только начинала распространяться в ходе становления раннеклассовых отношений. С этим, очевидно, было связано то обстоятельство, что наиболее ранние свидетельства о принятии мусульманства правителями Нусантары относятся не к яванским и юговосточносуматранским областям, где позиции махаяны и шиваизма, сплавленных с автохтонными культами, были весьма устойчивы, а к Северной Суматре.
Последняя четверть XIII—XIV вв. — это начальный, «домалаккский» период в истории исламизации австронезийских государств. Широкие масштабы и устойчивость этот процесс стал приобретать после появления султаната Малакка (с первой половины — середины XV в.). Но определенный комплекс внутренних условий и предпосылок этого феномена сложился кое-где в Западной Нусантаре еще в раннемаджапахитскую эпоху.
После распада Шривиджаи и утраты этой державой ее прежнего экономического и политического значения китайско-индийская торговля и региональный экспорт стали все более сосредоточиваться в малайских портах северо-западного и восточного побережья Малайи и Северной Суматры. Сюда кроме массы транзитных (ближневосточных и дальневосточных) товаров стекались широкоизвестные и высоко ценимые предметы индонезийского вывоза: алоэ, корица, олово и т. д. С ростом торгово-ремесленного населения и местной городской элиты, связанной с внешнеторговыми доходами, с притоком иммигрантов создавалась социальная среда, в значительной степени оторванная от старой традиционной культуры. Эта среда была более восприимчивой к проповеди идей и принципов ислама, которая усиливалась вместе с расширением числа приезжих мусульманских купцов и законоучителей, особенно из Индии.
Часть правящего класса малайских государств оказалась заинтересованной в новой религии, способствовавшей сплочению их интересов с интересами заморского купечества и влиятельных мусульманских кругов. Вместе с тем ислам в большей степени, чем старые классовые религии, был обращен к народным массам, куда проникал через городскую среду. В этих условиях принятие исламской веры правителями княжеств служило средством укрепления социально-политической опоры их власти, их харизматического статуса среди подданных и союзников. Ислам также означал не только новые, унифицированные и массовые религиозно-культовую практику и догматику, но и большую свободу духовенства от государственной политики, в отличие от старой системы с характерным для нее сращением светской и духовной власти. Становление исламизированных режимов произошло раньше на северо-восточном побережье Суматры (княжества Самудра, Педир, Перлак, Ару), чем на Малаккском полуострове. Эта область была в меньшей степени связана с государственными и идеологическими традициями Шривиджаи и яванских государств. Вместе с тем для господствующего класса, торговой верхушки и купеческих общин северосуматранских княжеств обращение к новой вере, к исламской идеологии было средством противостояния как яванскому диктату, так и сиамской агрессии.
Венецианец Марко Поло, который в течение почти полугода пробыл на Северной Суматре, в своих записках, относящихся к началу 1292 г., сообщает о недавнем обращении «купцами-сарацинами» в ислам государства «Ферлек» (Перлак). Из этого источника следует, что в Перлаке население уже было обращено в веру пророка, но за его пределами исламизация только развертывалась. Однако сравнительно скоро ислам утверждается и в другом центре Северной Суматры — Самудре. Можно полагать, что правитель Самудры принял мусульманскую веру в 1294 г., когда он породнился с правителем Перлака, женившись на его дочери. К 1297 г. относится надгробье этого неофита ислама и его новое имя — Малик-аль-Салех.
Когда Марко Поло посетил Суматру, имперская система Шривиджаи уже не существовала, и по сведениям венецианца на острове было восемь портовых княжеств, включая Мелаю. Происходило более интенсивное заселение южных областей Малаккского полуострова, что приводило к появлению новых торговых и сельскохозяйственных очагов.
Когда полвека спустя, в 1345—46 гг. известный арабский путешественник Ибн Баттута дважды посетил Самудру, то он обнаружил богатое торговое государство, во главе с султаном, исповедовавшим ортодоксальный ислам шафиитского толка (как и у большинства современных мусульман Юго-Восточной Азии). Вместе с другим торговым поселением, Пасэем, Самудра образовало государство, ставшее затем известным преимущественно как султанат Пасэй. Ко времени Ибн Баттуты, незадолго до того, как Пасэй подвергся маджапахитскому завоеванию (ок. 1360 г.), он сам вел войны с соседями, утверждая торжество ислама. Расширялась его роль в посреднической торговле; его авторитет как центра мусульманского богословия, исламизированной малайской культуры продолжал расти и после яванской экспансии, во многом являясь ориентиром развития блестящих культурных традиций Малаккского султаната.