Венецианец Марко Поло, который в течение почти полугода пробыл на Северной Суматре, в своих записках, относящихся к началу 1292 г., сообщает о недавнем обращении «купцами-сарацинами» в ислам государства «Ферлек» (Перлак). Из этого источника следует, что в Перлаке население уже было обращено в веру пророка, но за его пределами исламизация только развертывалась. Однако сравнительно скоро ислам утверждается и в другом центре Северной Суматры — Самудре. Можно полагать, что правитель Самудры принял мусульманскую веру в 1294 г., когда он породнился с правителем Перлака, женившись на его дочери. К 1297 г. относится надгробье этого неофита ислама и его новое имя — Малик-аль-Салех.
Когда Марко Поло посетил Суматру, имперская система Шривиджаи уже не существовала, и по сведениям венецианца на острове было восемь портовых княжеств, включая Мелаю. Происходило более интенсивное заселение южных областей Малаккского полуострова, что приводило к появлению новых торговых и сельскохозяйственных очагов.
Когда полвека спустя, в 1345—46 гг. известный арабский путешественник Ибн Баттута дважды посетил Самудру, то он обнаружил богатое торговое государство, во главе с султаном, исповедовавшим ортодоксальный ислам шафиитского толка (как и у большинства современных мусульман Юго-Восточной Азии). Вместе с другим торговым поселением, Пасэем, Самудра образовало государство, ставшее затем известным преимущественно как султанат Пасэй. Ко времени Ибн Баттуты, незадолго до того, как Пасэй подвергся маджапахитскому завоеванию (ок. 1360 г.), он сам вел войны с соседями, утверждая торжество ислама. Расширялась его роль в посреднической торговле; его авторитет как центра мусульманского богословия, исламизированной малайской культуры продолжал расти и после яванской экспансии, во многом являясь ориентиром развития блестящих культурных традиций Малаккского султаната.
И внешние и внутренние источники, содержащие сведения о государстве Маджапахит, позволяют считать, что период 20-х — 70-х гг. XIV в. был в его истории временем экономического и политического подъема, больших территориальных приобретений, на основе которых сформировалась обширная и сильная межостровная держава.
Францисканский монах, итальянец Одорико де Порденоне в записках о своих путешествиях писал в 1323 г. о Маджапахите как о густонаселенной и очень богатой стране. Но в его сведениях привлекают внимание три обстоятельства. Во-первых, что под властью «царя Явы» находятся семь других властителей. Это очень похоже на семерых прабху из монаршей семьи, входивших в высший совет при особе государя и деливших верховную власть как протекторы крупнейших областей Восточной и Центральной Явы. Другие источники подтверждают укрепление позиций королевского клана в управлении страной. Во-вторых, отмечается, что государство это неоднократно побеждало великого хана монголов (отзвуки событий четвертьвековой давности, связанных с провалом экспедиции монголо-китайских войск на Яве, будоражил воображение информаторов Одорико). В-третьих, обращают на себя внимание признаки расцвета яванской культуры того времени, индуистско-буддийской синкретической идеологии; автор уделяет особое внимание богатству резиденции монарха в столице.
После короткого правления вдовствующей королевы Гаятри (вдовы Джаянагары) в Маджапахите в 1329 г. воцарилась молодая яванская принцесса Трибхувана, единокровная сестра Джаянагары. Трибхувана более двадцати лет твердо удерживала власть, вручив своему сыну управление одной из ключевых центральных областей, Кахурипаном. Ее сестра, младшая дочь Гаятри, управляла Дахой, другим важнейшим уделом. При королеве Трибхуване (1329—1351) в начале ее царствования центральной властью были подавлены очаги местного восточнояванского сепаратизма: это были выступления в районах Саденг и Кета, куда направлялись маджапахитские войска под личным руководством Трибхуваны (1331 г.). Вместе с тем, как свидетельствуют надписи, власть яванской монархии распространялась в это время за пределы острова Ява, на Мадуру и на южное побережье Калимантана; о подчинении Маджапахиту других областей к началу 30-х гг. столетия судить трудно. Однако внутрияванский объединительный процесс, достигнутый уровень экономической, культурной и политической консолидации маджапахитского ядра сделали возможными новые усилия по «собиранию» Нусантары, осуществление паниндонезийской политики правящего класса.