Тем временем Агунг продолжал свое наступление на Восточной Яве. В 1617 г. пала столица княжества Пасуруан, а князь Пасуруана бежал в Сурабаю. В 1619 г. Агунг осадил главный порт Восточной Явы — Тубан. Сурабая и Мадура не смогли оказать тубанцам существенной поддержки. Тубан был взят штурмом и сильно разрушен, после чего он навсегда потерял свое прежнее значение.
В 1620 г. Агунг начинает серию походов непосредственно против Сурабаи. Первые две компании — в 1620 и 1621 гг. — кончились для него неудачно, потому что голландские корабли крейсировали вдоль Восточной Явы и прикрывали Сурабаю и Мадуру от нападения с моря. Тогда Агунг решил вступить в новые переговоры с голландской Ост-Индской компанией. Он освободил часть арестованных голландцев и в июне 1622 г. направил в Батавию посольство во главе с регентом (правителем) Тегала. Регент Тегала от имени Агунга предложил Куну военный союз против общего врага — Бантама. Куна и руководство Компании в Батавии, однако, не устраивал полный разгром Бантама. Они нуждались в нем, как в некоем противовесе растущей силе державы Агунга. Тем не менее они направили к Агунгу посольство во главе с Хендриком де Хааном, которое прибыло в столицу Матарама Карту 11 августа 1622 г. Военный союз против Бантама заключен не был, и все же Агунг в одностороннем порядке обещал поддержать Батавию, в случае если на нее нападет Бантам, и передал де Хаану для вручения Куну свой личный крис. Матарам обязался бесперебойно поставлять в Батавию рис, а голландцы обещали больше не оказывать поддержки Сурабае и Мадуре [134, с. 78; 158, с. 241; 242, с. 157].
Теперь Агунг смог обрушиться на южнокалимантанское княжество Сукадану, вассала Сурабаи. После завоевания Сукаданы (правительница которой была увезена в Матарам) флот Агунга вернулся на Яву и атаковал Гресик, который был взят и разрушен в том же, 1622 г. В 1623 г. флот Агунга появился у берегов Суматры. Князья Джамби и Палембанга на Южной Суматре поспешили признать себя вассалами Матарама. Вассалом Агунга признало себя и княжество Чиребон на Западной Яве. В 1624 г. матарамские морские силы атаковали Мадуру. Князья Сампанга, Бангкалана и Суменепа, союзники Сурабаи, выступили на защиту своего острова, но потерпели тяжелое поражение. Правящие семьи Мадуры были истреблены либо вывезены в Матарам. Агунг оставил на Мадуре только князя Сампанга, которого он объявил своим наместником на острове. Реальная власть, однако, находилась в руках приставленного к наместнику матарамского губернатора. Воодушевленный этими успехами Агунг принял в 1624 г. титул сусухунан — «тот, кому все покоряются» [158, с. 216; 209, с. 39–40; 263, с. 129].