През 1511 г. Малака пада в ръцете на португалците и султан Махмуд Шах е принуден да избяга от Малака.Султанът прави няколко опита да си върне столицата, но усилията му са безплодни.Португалците отвръщат и принуждават султана да избяга в Паханг.По-късно султанът отплавал до Бинтан и основал там нова столица.С установена база султанът събра разстроените малайски сили и организира няколко атаки и блокади срещу португалската позиция.Базиран в Пекан Туа, Сунгай Телур, Джохор, Джохорският султанат е основан от Раджа Али Ибни Султан Махмуд Мелака, известен като Султан Алаудин Риаят Шах II (1528–1564), през 1528 г. ^[53] Въпреки че султан Алаудин Риаят Шах и неговият наследник трябваше да се борят с атаките на португалците в Малака и на ачехите в Суматра, те успяха да запазят властта си над султаната Джохор.Честите набези на Малака причиниха на португалците сериозни трудности и помогнаха да бъдат убедени португалците да унищожат силите на изгнания султан.Бяха направени редица опити за потискане на малайците, но едва през 1526 г. португалците окончателно изравниха Бинтан със земята.След това султанът се оттегля в Кампар в Суматра и умира две години по-късно.Той остави след себе си двама сина на име Музафар Шах и Алаудин Риаят Шах II.^[53] Музафар Шах продължи да установява Перак, докато Алаудин Риаят Шах стана първият султан на Джохор.^[53]