От этого удара Матарам так и не оправился, но один уцелевший принц создал блистательное, хотя и недолговечное государство-преемника. После того как он провел четыре года в изгнании в монастыре, ему в 20-летнем возрасте предложили престол. Аирлангга быстро восстанавливал разрушенное, устроив новую базу неподалеку от современной Сурабаи, перегораживая плотинами реки, расширяя планы ирригации. Когда в 1049 году он умер, его империя распалась на два соперничающих королевства. Со временем одержало верх Сингасари, основанное в 1222 году сиротой, вором и легендарным героем Кен Ароком, когда он разгромил другое королевство, Кедири. Эту-то новую державу и унаследовал Кертенагара — довольно непрочное наследие, поскольку его выживание зависело как от сохранения контроля над торговлей пряностями, так и от постоянного наблюдения за Кедири и его мятежниками, которые обязательно должны были появиться. Честолюбиво стремясь к большему — в самом деле, сегодня некоторые видят в нем предтечу индонезийства, — он заключил союз с Тьямпой, женившись на тьямской принцессе, но в 1284 году потерпел неудачу с захватом Бали и, в другой стороне, кусочка Суматры.
Таким образом, Кертенагара был не очень доволен жизнью, когда в 1289 году прибыл посол от Хубилая по имени Мэн Чи, привезя с собой грубое требование подчиниться. Кертенагара наказал Хубилая за неуважение, приказав нанести татуировку на лицо посла, чтобы, когда тот, вернувшись ко двору, докладывал о результатах миссии, оскорбление было ясным и публичным. Это требовало возмездия. Хубилай приказал подготовить на юге боевой флот под командованием Ши-пи, ветерана сунской кампании. Под его общим руководством наземными войсками командовал Гао Син, а силами флота — уйгур по имени, звучащем вроде бы как Их-Мусу. Хубилай сказал им, что победят они без труда: «Если вы займете ту страну, другие меньшие государства сами покорятся, вам понадобится лишь отправить послов, чтобы принять их покорность». Три года они накапливали силы в Гуанчжоу (Зайтоне): 1000 кораблей, 20 000 солдат, запас зерна на год, 1000 килограммов серебра для покупки новых припасов.
Поэтому у Кертенагары в избытке хватало времени для подготовки к нападению — однако он неверно понял стратегию Ши-пи. Полагая что командующий будет продвигаться на юг вдоль побережья, заходя в порты как Тьямпы, так и Малайи, он отрядил силы, чтобы устроить там засаду монгольскому флоту. Это оказалось роковой ошибкой — 4000 км до Явы Ши-пи покрыл без остановок. Это была стратегия высокого риска — «Ветер дул сильный, а море очень бурлило, поэтому корабль сильно качало, и солдаты много дней не могли есть», — но она окупилась. В 1293 году Ши-пи высадил свои войска, не встретив никакого противодействия, поскольку в это самое время Кертенагара ввязался в войну с соседним государством Кедири и погиб. Все местные войска сражались на юге.
При таких обстоятельствах Ши-пи полагалось бы одержать легкую победу, обещанную Хубилаем. Но на деле он сразу же оказался втянут в водоворот местной политики. Зять Кертенагары Виджайя, равно честолюбивый, но куда менее прямолинейный, чем его тесть, отправил Ши-пи послание, предлагая свое подчинение в обмен на помощь против Кедири, и подкрепил свое предложение подарками в виде ладана, духов, рога носорога и слоновой кости. Ши-пи согласился. Виджайя прислал подробное описание территории — на реке Брантас, у подножия горы Уиллис, в 105 км к юго-западу от Сурабаи, богата рисом, с портом на побережье; к описанию прилагалась подробная полезная карта. Монголы вступили в войну. Через неделю 5000 кедирийских солдат погибли, их предводитель был казнен, а территория попала в руки Ши-пи.
Оставалось только провести церемонию, отпраздновав победу, и, конечно, принять обещанную Виджайей покорность. Виджайя попросил дать ему эскорт из 200 безоружных солдат, чтобы сопроводить его в столицу Маджапахит, предположительно для доставки подарков. Но по дороге люди Виджайи убили безоружный эскорт, а затем напали на монгольское войско. Ши-пи был вынужден бежать обратно к кораблям, с арьергардными боями сделав 150-километровый бросок к побережью, и отправился домой — а там Хубилай вознаградил его за провал и потерю 3000 солдат 17 легкими палками и конфискацией трети принадлежавшей ему собственности.