Sama seperti kebanyakkan petempatan awal, kebanyakkan penduduk Kelantan tertumpu di kiri kana Sungai Kelantan dan anak-anak sungainya. Raja dan pembesar Kelantan mula membina kubu-kubu istana di kuala-kuala dan juga di sepanjang sungai bagi memudahkan kerja-kerja mengutip cukai. Keadaan ini telah mendorong kebanyakkan rakyat tinggal di kuala kerana di situ barang-barang lebih murah kerana tidak dikenakan cukai berbanding dengan harga barang-barang di kawasan pendalaman.

Kota Bharu, ibu negeri Kelantan, secara rasminya dibuka oleh Sultan Muhammad II pada tahun 1844. Akan tetapi kawasan petempatan di situ dipercayai telah diterokai lama sebelum itu.

Apabila Sultan Muhammad I mangkat pada tahun 1835, Long Zainal mengisytiharkan dirinya sebagai Sultan Kelantan. Long Senik yang telah diwasiatkan sebagai Sultan Muhammad I telah diketepikan dan hanya diberi gelaran Temenggung Aria Pahlawan. Dalam tahun 1835-1836 tercetus perang saudara di Kelantan di antara pihak Long Zainal dengan pihak Raja Bendahara. Dalam peperangan itu, Long Zainal telah kalah. Berikutan itu, pada tahun 1837, Raja Siam telah memperkenankan Long Senik Mulut Merah menjadi raja Kelantan, bergelar Sultan Muhammad II. Baginda juga dikenali sebagai Marhum Tua. Baginda merupakan sultan yang paling lama memerintah negeri Kelantan, kira-kira 49 tahun.

Selepas berlakunya perang saudara di Kelantan pada tahun 1837, Baginda telah berpindah dari istana di Kota Sekebun Semesta ke suatu tempat di sebelah tebing kiri di hilir Sungai Kelantan. Baginda telah mendirikan sebuah kota dan sebuah istana kayu yang besar di tampat itu. Istana Kayu yang dibina sebagai Istana Balai Besar.

Istana Balai Besar diilhamkan daripada seni bina istana raja-raja Melayu yang terdapat di Pattani, Thailand dengan pengaruh unsur seni bina Jawa. Kayu yang digunakan ialah kayu Cengal. Tukang kayu yang bertanggungjawab dalam pembinaan bangunan istana ini dikenali sebagai Salleh. Bangunan ini menjadi tempat bersemayam Sultan Muhammad II sehinggalah baginda mangkat pada 1886.

Selepas itu Istana Balai Besar menjadi tempat bersemayam putera baginda yang sulung, Long Ahmad yang diangkat menjadi Sultan Kelantan menggantikan ayahanda baginda. Sultan Ahmad mangkat pada tahun 1889 dan putera baginda yang bernama Tengku Kundur dilantik menjadi Sultan Kelantan, bergelar Sultan Muhammad III. Majlis pertabalan baginda diadakan di Istana Balai Besar.

Long Senik dilantik menjadi sultan selepas kemangkatan Sultan Mansur pada tahun 1900. Baginda memakai gelaran Sultan Muhammad IV (1900-1920). Istiadat pertabalan baginda diadakan di Istana Balai Besar tetapi baginda bersemayam di Istana Jahar.

Istana Jahar terletak berhampiran dengan Istana Balai Besar. Istana ini dibina oleh Sultan Muhammad II pada tahun 1886 untuk cucunda baginda, Long Kundur yang dilantik menjadi Raja Bendahara. Oleh sebab itu istana ini dulunya dikenali sebagai Istana Raja Bendahara. Pada tahun 1920, Sultan Muhammad IV menukarkan nama itu kepada Istana Jahar, mengambil sempena nama sebatang pokok yang hanyut lalu masuk ke dalam kawasan istana semasa berlaku banjir besar. Selepas kejadian itu, beberapa batang pokok Jahar di tanam di perkarangan istana. Sejak itu Istana Jahar menjadi tempat bersemayam sultan-sultan yang memerintah Kelantan seterusnya sehingga Sultan Yahya Putera berpindah ke sebuah istana baru. Kini Istana Jahar dijadikan Muzium Negeri Kelantan.

Di belakang Istana Jahar terdapat sebuah istana lain, Istana Seri Akar. Istana ini dibina pada akhir pemerintahan Sultan Muhammad II untuk dihadiahkan kepada cucunda baginda yang bernama Tengku Kembang Puteri atau ringkasnya Tengku Puteri.

Istana Akar terkenal sebagai tempat bersemayam bekas raja Melayu Pattani yang sudah tidak mempunyai negeri. Tengku Puteri berkahwin dengan dua orang raja Pattani, iaitu Tengku Putih dan selepas kemangkatannya pada tahun 1905, Tengku Abdul Kadir. Istana ini kemudiannya diwariskan kepada putera Tengku Puteri, Tengku Zainal Abidin yang bergelar Seri Akar Diraja. Apabila Tengku Seri Akar mangkat pada tahun 1933, istana ini ditinggalkan kepada puterinya yang bernama Tengku Muniratul Sahiah. Sejak tahun 1960-an, Istana Seri Akar tidak lagi diduduki.

Kini seluruh bangunan istana itu mengalami kerosakan dan yang tinggal hanya bangunan Balai Penghadapan.

Sejak terdirinya Istana Balai Besar di Buluh Kubu dalam tahun 1844 Masihi, rakyat mula membuat rumah-rumah kediaman dan kampung halaman mereka masing-masing di sebelah hilir dan hulu kawasan Buluh Kubu atau Dalam Kubu, sehingga lama-kelamaan menjadi perkampungan yang besar. Di zaman permulaannya, Kota Bharu merupakan sebuah bandar yang kecil lagi sempit kawasannya, mungkin didiami oleh antara 3000-5000 orang sahaja. Kawasan penting dan yang agak penuh sesak didiami orang pada zaman permulaannya ialah kawasan hilir bandar Kota Bharu yang lebih dikenali dengan nama Kampung Masjid dan Kubang Pasu atau Balik hilir dan kawasan hulu yang meliputi Jalan Haji Cik Su (Kampung Gajah Mati) dan Jalan Tok Hakim sekarang ini. Pusat perniagaan dan pasar Kota Bharu mula-mulanya terletak di kawasan tepi Sungai Kelantan kira-kira di sekitar Taman Sekebun Bunga sekarang ini (di sebelah hilir panggung Lido sekarang). Di luar kawasan-kawasan yang tersebut itu pada masa itu ialah tanah belukar dan padang.

Pada tahun 1926 Masihi bandar Kota Bharu mula menggunakan api elektrik yang dibekalkan oleh sebuah jentera sederhana yang ditempatkan di sebuah bangunan di Jalan Tok Hakim berhampiran dengan Pasar Besar Kota Bharu. Pada masa sekarang ini ibu sawat api elektrik adalah terletak di Lundang Jalan Pasir Puteh. Bekalan api elektrik mula di gunakan dalam bandar Kota Bharu pada akhir tahun 1926 Masihi dan mulai daripada awal tahun 1927 Masihi lampu-lampu minyak jalan raya dalam bandar Kota Bharu beransur-ansur digantikan dengan api elektrik yang dikendalikan oleh Jabatan Kerja Raya.

Kota dan istana baru itu dibina di atas sebidang tanah seluas lebih kurang empat ekar dan disekelilingnya dibina pagar kayu daripada jenis kayu cengal setinggi kira-kira sepuluh kaki. Pagar kayu itu berbentuk empat persegi. Pagar atau dinding bahagian hadapan yang terletak di sebelah matahari jatuh (sebelah barat) mempunyai tiga pintu iaitu satu pintu gerbang besar di tengah-tengahnya yang merupakan pintu utama dan dua pintu kecil di kiri kanan pintu gerbang besar itu. Bahagian hadapan bangunan istana itu berbentuk sebuah balai yang besar tiada berlantai tetapi mempunyai tiga lapis atau tingkat dan bumbungnya pula tiga tingkat juga. Bumbung asal diperbuat dari batang-batang kayu cengal dan beratap daun nipah yang baik jenisnya. Balai yang besar itu mempunyai banyak tiang bulat juga daripada jenis kayu cengal manakala lantainya dibina daripada keping-keping batu bata merah yang diperbuat daripada tanah liat yang baik mutunya yang didatangkan daripada negeri Patani. Bahagian belakang istana itu (iaitu di belakang balai besar itu) ialah sebuah rumah basar yang diperbuat daripada kayu yang merupakan istana khususnya untuk kediaman raja. Di sebelah hulu istana balai besar itu dibina pula sebuah surau dan juga sebuah rumah tempat pengawal-pengawal raja. Adapun bangunan istana dan balai besar itu berbentuk bangunan tradisi Melayu Kelantan/Patani.

Mengikut cerita orang tua-tua Kelantan kepala tukang-tukang yang ditugaskan membina Istana Balai Besar itu ialah seorang tukang yang masyur di zaman itu berasal dari Terengganu bernama Muhammad Salleh yang menetap di Kampung Kangkung, dalam jajahan Pasir Mas sekarang. Beliau adalah satu-satunya tukang rumah dan juruukir yang pintar dan ulung di Abad ke-19 Masihi yang lalu.

Kota dan istana balai besar 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.

Bentuk Istana Balai Besar itu kekal tidak berubah hingga ke masa sekarang ini, melainkan bahagian hadapan dan balai penghadapan saja telah dipinda dalam zaman pemerintahan Sultan Muhamad IV (1900-1920 Masihi) disamping beberapa tambahan yang telah dibuat dalam zaman pemerintahan Sultan Ismail (1921-1944 Masihi).

Istana Balai Besar ini telah menjadi tempat berlangsungnya segala upacara dan adat istiadat yang kecil dan besar serta bersejarah sejak dari tahun 1845 Masihi sehingga kepada masa sekarang ini, seperti upacara istiadat pertabalan atau kemahkotaan, pengurniaan gelaran kebesaran dan bintang-bintang, perkahwinan diraja, sambutan tetamu atau pembesar-pembesar dari luar negeri, istiadat ulang tahun diraja atau "Puja Umur", upacara istiadat menjunjung duli dan lain-lain lagi.

Istana Balai Besar telah didiami oleh beberapa orang Sultan Kelantan. Sultan Muhammad II (Long Senik bin Long Tan) yang memerintah Kelantan dari tahun 1839 hingga tahun 1886 Masihi bersemayam di Istana Balai Besar. Kemudian didiami pula oleh tiga orang Sultan iaitu Sultan Ahmad (Tuan Ahmad bin Tuan Senik Mulut Merah) yang memerintah Kelantan antara tahun 1886 hingga tahun 1889 Masihi; Sultan Muhamad III (Tuan Kundor bin Tuan Ahmad) yang memerintah Kelantan antara tahun 1890 hingga tahun 1891 Masihi.