Lepaih Portugis tawan Melaka pada 1511, keghajaan Melayu hat sambung Kesultanan Melaka tu pindah ke Johor. Pada 1540, Sultan Alauddin Riayat Shah II, Sultan Johor kedua, bina Kota Batu kat Johor Lama jadi pusat pentadbiran keghajaan Johor.
Kota ni duduk ataih bukit kat tebing kiri Sungai Johor. Sebahagian dia dikenali sebagai Tanjung Batu sebab tanjung dia curam. Bentuk dia segi empat tepat, 50 meter panjang, 20 meter lebaq, dengan beberapa penjuru hat dibina khaih untuk pertahanan. Binaan dia blok batu padu, ditimbuih tanah kat ataih, lengkap dengan senjata dan meriam.
Sejaghah perang dia panjang. 1564, Aceh seghang dan tawan kota ni — Sultan Alauddin II ditawan dan mangkat dalam tawanan. Sultan Ali Jalla Abdul Jalil Riayat Shah pulihkan semula kota tu. Portugis mai seghang 1576, ditahan. Mai lagi 1578, ditahan. 1586 pun sama, ditahan jugak.
Tapi 1587 lain ceghita dia. Tahun tu Sultan Ali sendighi hat pi seghang kubu A Famosa kat Melaka, dan gagal. Portugis balas balik — dengan bantuan tambahan dari Goa, depa seghang dan tawan Kota Batu.
Jadi kubu selebaq dua puluh meter ni bertahan 47 tahun lawan Aceh dan Portugis, dan akhirnya tumbang bukan sebab kena seghang ja — tapi sebab tuannya seghang dulu dan kalah. Ceghita Johor lepaih tu, bila pusat pentadbiran pindah ke Batu Sawar, tu ceghita lain.
