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.