В 1412 г. к императорскому двору прибыло новое малакк-ское посольство во главе с племянником Парамешвары. Официально его целью было выражение благодарности за оказанный в прошлом году прием. На деле, видимо, малаккский властитель пытался добиться от императора возвращения своего родового владения — княжества Палембанг на Суматре. Однако китайское правительство, последовательно проводившее политику фрагментации государств Юго-Восточной Азии, не было заинтересовано в чрезмерном укреплении своего нового вассала и предпочло оставить Палембанг под номинальным сюзеренитетом сильно ослабевшего Маджапахита. Малаккское посольство вернулось обратно ни с чем [280, с. 47].
Предприимчивый Парамешвара не примирился с этим отказом. В 1413 г. он направил королю Маджапахита подложный указ, составленный якобы от имени Чжу Ди, с требованием передать ему (Парамешваре) Палембанг. Подлог был раскрыт находившимся в это время на Яве китайским послом У Цином. Император Чжу Ди по этому поводу направил в Маджапахит следующее послание: «Недавно стало известно, что Малакка требует возврата земли Палембанга, а ван Явы (король Маджапахита. —
Таким образом, Парамешвара попал в немилость у китайского двора. Он, однако, не оставил своих планов установить гегемонию в малайско-суматранском районе. С этой целью он решил опереться на новую силу, сравнительно недавно здесь появившуюся, — мусульманство, занесенное купцами из Индии и Аравии. Мусульманскими в этом районе к началу XV в. были несколько торговых городов-государств на Северо-Восточной Суматре. Крупнейшим из них был султанат Пасей, одноименный порт которого в XIV в. был главным центром торговли в проливах. В первые годы существования Малакки ее отношения с Пасеем, могучим конкурентом, были натянутыми. Томе Пиреш сообщает, что Парамешвара (видимо, около 1410 г.) арестовал прибывших к нему послов Пасея и держал под стражей три года [229, т. II, с. 240]. Теперь владетель Малакки резко изменил курс, освободил послов, установил дружбу с султаном Пасея, женился в возрасте 72 лет на его дочери и принял ислам вместе со своими приближенными.
Большинство историков считает, что переход Парамешвары в ислам произошел в 1414 г. [54, с. 44; 56, с. 157; 209, с. 123]. Однако переводчик 4-й экспедиции Чжэн Хэ Ма Хуань, который сам был мусульманином, посетивший Малакку в 1413 г., сообщает, что он видел Парамешвару с белым тюрбаном на голове и что все жители страны, так же как король, мусульмане [185, с. 110]. По-видимому, Парамешвара сменил религию сразу же после, фиаско с Палембангом.
Перейдя в ислам, Парамешвара принял имя Мегат Искандер-шах. Это звучное имя должно было не только прибавить ему популярности в международных мусульманских кругах. В 1414 г. он вновь отправился в Китай и, видимо, дал крупную взятку тамошним чиновникам, потому что они занесли в соответствующие документы, что в Китай прибыл Исыганьдерша, чтобы сообщить о смерти своего отца — вана Малакки Парамешвары и получить новую инвеституру на трон Малакки. Это внесло путаницу в построения позднейших историков, но сняло с него опалу императора, поскольку, выступая в качестве собственного сына, он, естественно, не отвечал за преступления отца [15, с. 95; 56, с. 157; 229, т. II, с. 245].
Утверждение мусульманства способствовало новому притоку мусульманских купцов различных наций в Малакку. Как сообщает Т. Пиреш, «много богатых маврских купцов перешли из Пасея в Малакку. Здесь были персы, бенгальцы, арабы. В то время большинство купцов принадлежало к этим трем нациям. Они были очень богаты и привезли с собой своих мулл. Они сказали, что готовы платить подати, ибо стало известно, что люди Явы хотят привозить сюда гвоздику, мускатный орех, мускатный цвет и сандал… Хакем Даркса (Мегат Искандер-шах) оказал им почести, дал землю для постройки домов и мечетей. Торговля стала быстро расти благодаря этим богатым маврам. И так же быстро стали расти доходы короля…И с Суматры стали прибывать люди, начали работать и зарабатывать на жизнь, и из Сингапура, и с ближних островов селатов, и из других мест. И так как король был справедлив и шедр к купцам, его любили» [229, т. II, с. 240–241].
Звезда Пасея стала постепенно закатываться, в то время как звезда Малакки всходила все выше. Однако растущее богатство Малакки не могло не привлекать внимания Сиама. В 1419 г. Парамешвара (Мегат Искандер-шах), несмотря на преклонный возраст, снова лично отправился в Китай с просьбой оградить его от сиамской агрессии [209, с. 124].