Muzium ini telah ditubuhkan pada tahun 1990 bertempat di bangunan lama Majlis Perbandaran Kota Bharu, Jalan Hospital yang telah diwartakan sebagai salah sebuah bangunan bersejarah dibawah Akta Warisan Kebangsaan 2005 (AKTA 645)

Muzium Negeri telah dirasmikan pembukaannya oleh KDYMM Al-Sultan Kelantan pada 6 Ogos 1990. Muzium Negeri terletak bersebelahan Bulatan (Medan) Tuan Padang dalam kompleks bangunan Pejabat Tanah dan Jajahan Kota Bharu. Dalam kompleks yang sama juga terletak Pusat Penerangan Pelancongan Negeri Kelantan (T.I.C).

Bangunan Muzium Negeri Kelantan adalah sebuah bangunan batu. Sebelum dijadikan Muzium ianya merupakan pejabat bagi Majlis Perbandaran Kota Bharu. Bangunan tersebut telah dibaikpulih dan dibuat beberapa perubahan sesuai dengan sebuah Muzium.

Tahun 1988 bahagian dalam bangunan Muzium ini telah diubah dengan menambah setengah tingkat lagi dan menyediakan ruang-ruang untuk membahagikan aliran cerita yang ditetapkan bagi Muzium ini. Aliran pameran Muzium negeri ini ruang awalnya mempamerkan sejarah negeri Kelantan semenjak awal hingga kepada era moden. Pada bahagian setengah tingkat di atas pula diadakan pameran mengenai Seni Budaya Negeri Kelantan termasuklah peralatan permainan wayang kulit, rebana ubi, makyong, menora dan lain-lain. Pada bahagian bawah bangunan pula selain ditampilkan Sejarah Negeri Kelantan ditempatkan juga pejabat am Perbadanan Muzium Negeri Kelantan, Pejabat Pengarah Muzium dan lain-lain bahagian.

Matlamat penubuhan Muzium Negeri ini ialah menampilkan sejarah dan budaya Negeri Kelantan untuk tatapan umum.

Bayaran masuk ke Muzium Negeri ialah RM2 untuk orang dewasa dan RM1 untuk kanak-kanak. Manakala pengunjung antarabangsa pula bayarannya ialah RM4 untuk orang dewasa dan RM2 untuk kanak-kanak. Muzium ini dibuka pada setiap hari kecuali hari Jumaat bermula jam 8.30 pagi hingga 4.45 petang.