Sultan baru mendirikan ibu kota baru di tepi Sungai Johor dan, dari sana, terus mengganggu Portugis di utara.Ia konsisten bekerja sama dengan saudaranya di Perak dan Sultan Pahang untuk merebut kembali Malaka, yang saat itu dilindungi oleh benteng A Famosa.Di Sumatera bagian utara sekitar periode yang sama, Kesultanan Aceh mulai memperoleh pengaruh besar di Selat Malaka.Dengan jatuhnya Malaka ke tangan Kristen, para pedagang Muslim seringkali meninggalkan Malaka dan memilih Aceh atau juga ibu kota Johor, Johor Lama (Kota Batu).Oleh karena itu, Malaka dan Aceh menjadi pesaing langsung.Ketika Portugis dan Johor sering saling adu mulut, Aceh melancarkan beberapa serangan terhadap kedua belah pihak untuk memperketat cengkeramannya atas selat tersebut.Kebangkitan dan perluasan Aceh mendorong Portugis dan Johor untuk menandatangani gencatan senjata dan mengalihkan perhatian mereka ke Aceh.Namun gencatan senjata tersebut tidak berlangsung lama dan dengan melemahnya Aceh, Johor dan Portugis kembali saling mengincar.Pada masa pemerintahan Sultan Iskandar Muda, Aceh menyerang Johor pada tahun 1613 dan kembali pada tahun 1615. ^[54]