Kemangkatan Sultan Muhammad I pada tahun 1835 Masihi. Apabila Sultan Muhammad I mangkat negeri Kelantan telah diperintah pula oleh Long Zainal (Long Jenal) adindanya sendiri. Long Jenal juga memakai gelaran Yang Dipertuan dan memerintah dari tahun 1835 hingga tahun 1839 Masihi. Zaman pemerintahan Long Jenal tidak aman kerana berlaku perang saudara antara baginda dengan putera-putera Long Hitam (Long Tan) yang dikepalai oleh Senik (dikenali juga sebagai Tuan Senik Muluk Merah atau Tuan Senik Kampung Sireh) juga adalah anakanda saudara kepada Long Jenal. Dalam perang saudara itu pihak Tuan Senik Mulut Merah akhirnya beroleh kemenangan. Dalam perang itu kedua-dua pihak yang bermusuhan masing-masing menghantar surat dan utusan kepada Raja Siam meminta sokongan dan campur tangan untuk menyelesaikan krisis politik di negeri Kelantan itu.
Setelah Raja Siam menghantar empat utusan ke negeri Kelantan, barulah krisis itu dapat diatasi. Pihak Siam menyokong serta memihak kepada pihak Tuan Senik Mulut Merah yang kebetulan pula beroleh kemenangan. Setelah berperang beberapa lama Long Jenal terpaksa melarikan diri ke Terengganu dan kemudiannya ke Menara (Bangnara atau Narathiwat sekarang). Berikutan dengan kekalahan Long Jenal itu Senik Mulut Merah menjadi Raja Pemerintah Kelantan dengan bergelar Sultan Muhammad II. Baginda memerintah Kelantan dari tahun 1839 hingga kepada tahun 1886 Masihi iaitu selama 47 tahun. Setelah mangkat baginda dikenali juga sebagai Marhum Mulut Merah.
Oleh kerana terletak di tepi sungai Kelantan yang agak besar juga itu serta selalu berlaku banjir setiap tahun, maka setelah sepuluh atau dua puluh tahun, Pulau Saba telah dimakan air dan runtuh sedikit demi sedikit tiap-tiap tahun sehingga membimbangkan baginda Sultan. Oleh sebab itu pada tahun 1840 Masihi Sultan Muhammad II (Tuan Senik Mulut Merah) telah memerintahkan supaya digali sebuah anak sungai di tebing sebelah barat Sungai Kelantan iaitu dari Kampung Kutan hingga ke bendang Mokrat (dekat Kampung Palekbang sekarang). Tujuan menggali anak sungai itu ialah untuk melarikan arus Sungai Kelantan di sebelah timur. Anak sungai itu telah selesai digali pada tahun 1841 Masihi dan merupakan satu cabang dari Sungai Kelantan dan panjangnya adalah kira-kira tiga batu. Tetapi anak sungai itu telah tertimbus dengan sekali banjir saja oleh pasir dan lumpur yang dibawa oleh arus banjir Sungai Kelantan. Namun demikian anak sungai tersebut hingga sekarang masih ada lagi bekasnya atau kesannya dan terkenal dengan nama Sungai Raja Gali.
Apabila Sungai Raja Gali itu telah tertimbus, maka tebing Sungai Kelantan, terutama sekali tebing sebelah timur, mulai runtuh kembali apabila berlaku banjir. Keruntuhan tebing-tebing sungai itu mengancam keselamatan kota atau bandar Pulau Saba itu termasuk juga kawasan yang dipanggil "Kebun Mengseta" di mana terletak beberapa rumah kerabat diraja Kelantan di zaman itu.
Oleh itu, Sultan Muhammad II telah memilih satu kawasan di pendalaman di sebelah timur Pulau Saba dan Kebun Mengseta serta diperintahkan supaya didirikan sebuah kota yang baru. Pembinaan kota itu telah dimulakan pada kira-kira tahun 1844 Masihi.
Pada asasnya tapak Istana Balai Besar itu sebahagian daripada satu kawasan besar yang meliputi kira-kira empat ekar yang di panggil "Buluh Kubu" kerana kawasan tersebut dikelilingi oleh deretan pokok-pokok buluh peleting yang ditanam sebagai pagar yang besar. Kawasan di dalam "Buluh Kubu" itu termasuk tapak Istana Balai Besar adalah menjadi hak Sultan yang memerintah secara turun-temurun. "Buluh Kubu" kemudiannya lebih terkenal dengan panggilan "Dalam Kubu".
Setelah kota itu siap dibina kira-kira pada tahun 1844 Masihi, Sultan Muhammad II pun berangkat dan bersemayam di kota serta istana yang baru itu. Kota dan istana itu pada mulanya dikenali atau dipanggil "Kota Bharu" mengambil sempena kota dan istana yang baru dibina itu. Ia segera berkembang menjadi pusat pemerintahan dan pentadbiran negeri Kelantan. Ia menjadi ibu negeri Kelantan di zaman moden ini. Oleh sebab terjadi kekeliruan dengan kerana nama kota istana itu dipanggil "Kota Bharu" dan ibu negeri Kelantan juga dipanggil "Kota Bharu", maka Sultan Muhammad II menitahkan supaya kota istana tempat Baginda bersemayam itu diberi nama yang lain pula iaitu "Istana Balai Besar" supaya berbeza dengan Kota Bharu yang menjadi nama bandar dan ibu negeri Kelantan.
