In 1511 het Malakka vir die Portugese geval en Sultan Mahmud Shah is gedwing om uit Malakka te vlug.Die sultan het verskeie pogings aangewend om die hoofstad terug te neem, maar sy pogings was vrugteloos.Die Portugese het wraak geneem en die sultan gedwing om na Pahang te vlug.Later het die sultan na Bintan gevaar en daar 'n nuwe hoofstad gevestig.Met 'n basis gevestig, het die sultan die onstuimige Maleise magte byeengeroep en verskeie aanvalle en blokkades teen die Portugese posisie georganiseer.Gebaseer te Pekan Tua, Sungai Telur, Johor, is die Johor Sultanaat gestig deur Raja Ali Ibni Sultan Mahmud Melaka, bekend as Sultan Alauddin Riayat Shah II (1528–1564), in 1528. ^[53] Alhoewel Sultan Alauddin Riayat Shah en sy opvolger met aanvalle deur die Portugese in Malakka en deur die Acehnese in Sumatra te kampe gehad het, het hulle daarin geslaag om hul houvas op die Johor-sultanaat te behou.Gereelde strooptogte op Malakka het die Portugese erge ontbering veroorsaak en dit het gehelp om die Portugese te oortuig om die verbanne sultan se magte te vernietig.'n Aantal pogings is aangewend om die Maleier te onderdruk, maar dit was eers in 1526 dat die Portugese Bintan finaal met die grond gelyk gemaak het.Die sultan het toe na Kampar in Sumatra teruggetrek en twee jaar later gesterf.Hy het twee seuns genaamd Muzaffar Shah en Alauddin Riayat Shah II agtergelaat.^[53] Muzaffar Shah het voortgegaan om Perak te stig terwyl Alauddin Riayat Shah die eerste sultan van Johor geword het.^[53]