На востоке и северном побережье Явы объединительная политика Сенапати встретила, однако, гораздо более упорное сопротивление. Восточнояванские княжества, самым сильным из которых была Сурабая, не признали правителя-«выскочку». Портовые города-государства Северной Явы — Джапара, Тубан, Гресик и другие, слабо связанные с экономически отсталыми районами внутренней Явы, на которые опирался Сенапати, также заняли враждебную позицию по отношению к Матараму. В 1589 г. Сенапати совершил первую попытку завоевания Восточной Явы. Он вторгся в область Джапан (совр. Маджакерта), где его войскам преградила путь коалиция восточных князей во главе с правителем Сурабаи Адипати. До генерального сражения, однако, дело не дошло. Князь-мулла духовного княжества Гири, которого европейские современники называли «мусульманский папа», предложил противникам свое посредничество. Согласно яванской летописи, он загадал им загадку — предложил сделать выбор между шкатулкой и содержащимися в ней драгоценностями. Сенапати выбрал шкатулку, и на основании этого князь-«папа» Гири якобы объявил его верховным правителем Явы (кому принадлежит шкатулка — тому принадлежит и содержимое). После этого, по словам летописца, князь Сурабаи признал номинальное верховенство Сенапати, и войска противников вернулись в свои земли [132, с. 103; 133, с. 104]. Эта история скорее всего является измышлением матарам-ских летописцев XVII–XVIII вв., имевших целью лишний раз подчеркнуть легитимность притязаний Сенапати на верховную власть. Чтобы свести концы с концами в дальнейшем изложении событий, они сами сообщают, что князь Сурабаи почти тут же «передумал» и борьба между Центром и Востоком Явы возобновилась с новой силой. В рассказе о третейском суде князя Гири имеется, однако, рациональное зерно. Духовные владыки Гири в XVI — первой половине XVII в. действительно пользовались на Яве огромным авторитетом и действительно могли агитировать за объединение страны против политического и религиозного врага — европейцев-христиан.
В 1590 г. против Сенапати выступил князь Мадиуна, который раньше тоже вроде бы признавал номинально власть Ма-тарама. Ему оказали военную поддержку князья Панарукана и Сурабаи. Сенапати лишний раз доказал, что в арсенале его средств дипломатия играла ничуть не меньшую роль, чем военное искусство. Он направил в Мадиун женщину-посла. Посланница сообщила князю Мадиуна, что Сенапати готов ему подчиниться. Завоевав расположение князя, она добилась частичного разоружения Мадиуна. После этого войско Сенапати нанесло короткий удар по Мадиуну и овладело его столицей. Князь Мадиуна, пытаясь бороться с Сенапати тем же оружием, оставил во дворце свою дочь, полагая, что она сможет одурачить матарамского правителя так же, как был одурачен ее отец. Но Сенапати был человеком другого склада. Он просто взял княжну в жены. Так как это был первый брачный союз Матарамского дома со старым правящим кланом Явы, матарамская пропаганда извлекла из него максимальную выгоду [209, с. 32].