FASA 1 - KERJA-KERJA INFRASTRUKTUR

Pelaksanaan kerja Fasa 1 telah dimulakan pada tahun 1985. Ia merangkumi kerja-kerja:

a. Penyediaan jalan-jalan masuk yang utama serta penyediaan longkang-longkang laluan masuk dan keluar air.
b. Pembinaan jambatan yang merentang alur sungai.
c. Penyediaan kemudahan tempat meletak kenderaan (parking space)
d. Membaiki dan memindahkan tapak surau Kg.Bukit Losong.
e. Kerja-kerja penyediaan dan pembaikian tanah untuk menstabil lereng-lereng bukit.

Kontraktor Seri Terukun Sdn. Bhd. telah dipertanggungjawabkan untuk melaksanakan kerja-kerja di Fasa 1.


FASA II - KERJA-KERJA SENI TAMAN

Pelaksanaan kerja Fasa II telah dilaksanakan pada tahun 1986 dan kerja-kerja di peringkat ini meliputi :
a. Penanaman pokok-pokok asas.
b. Penanaman pokok-pokok bungan hiasan.
c. Membaikpulih kawasan lereng-lereng bukit dengan membina retaining wall.
d. Membaikpulih kawasan di sepanjang tebing sungai dengan membina retaining boulder
e. Penyediaan laluan pejalan kaki ( footpath )

Di samping proses pelaksanaan kerja-kerja yang disenaraikan di atas, kerja-kerja Fasa II juga melibatkan kerja pemindahan dan penempatan semula empat buah rumah tradisional. Rumah-rumah tersebut termasuklah Istana Tengku Long dari Kg. Raja, Besut, Rumah Tele atau Istana Tengku Nik dari Kawasan Istana Maziah, Rumah Bujang Berpeleh dari Kg. Hiliran serta Rumah Hajjah Ngah Aishah dari Kawasan Istana Kolam. Rumah-rumah tersebut telah didirikan semula disatu kawasan di tapak Muzium Negeri, Bukit Losong. Kerja-kerja seni tanam di Fasa II ini telah disempurnakan oleh ASENA Landscape (Trg.) Sdn. Bhd.


FASA III - KERJA-KERJA PEMBINAAN MUZIUM MARITIM I
(GALERI PELAYARAN DAN PERDAGANGAN )

Kerja-kerja Fasa III telah dimulakan pada tahun 1988. Kerja-kerja ini merangkumi kerja pembinaan untuk menyiapkan dua (2) buah bangunan pameran berkaitan maritim. Di dalam Fasa III juga dilaksanakan kerja-kerja penempatan semula dua buah perahu besar, iaitu Sabar dan Kemajuan. Kontraktor yang bertanggungjawab melaksanakan kerja-kerja Fasa III ialah Daya Sinar Enterprise Sdn. Bhd.


FASA IV - KERJA-KERJA PEMBINAAN BANGUNAN UTAMA

Reka bentuk bangunan utama pada Fasa IV ini telah disemak beberapa kali semenjak tahun 1984. Hal ini berlaku disebabkan oleh masalah kewangan yang agak terbatas. Walau bagaimanapun, ia telah dapat ditender pada penghujung tahun 1989, manakala kerja-kerja pecah tanah ( ground breaking ) telah dilakukan pada tahun 1991 oleh Y.A.B. Dato' Setia Wangsa Dato' Haji Abdul Rahman Nasir, Setiausaha Kerajaan Negeri Terengganu merangkap Pengerusi Lembaga Muzium Negeri Terengganu pada masa itu.
Kontraktor utama yang dipertanggungjawab untuk menjalankan kerja-kerja Fasa IV ialah Seri Terukun Sdn. Bhd.


FASA V - KERJA-KERJA PEMBINAAN MUZIUM MARITIM
(GALERI PERIKANAN DAN TAMAN LAUT )

Kerja di dalam Fasa V merupakan kerja yang terakhir dilakukan. Ia merupakan kerja untuk menyiapkan sebuah bangunan dua (2) tingkat untuk menempatkan galeri mariti. Kerja pada Fasa V telah dilakukan oleh kontraktor daripada Syarikat Rafarjawan Sdn. Bhd.