Sejarah Sekolah Kebangsaan Melikai telah bermula dalam tahun 1967 sebuah bangunan mengandungi satu bilik darjah yang berukuran 30 x 20 didirikan di atas tanah milik kerajaan seluas 4 ekar bekas tapak tamu mingguan Kampong Melikai. Sekolah ini pada mulanya diasaskan oleh 2 orang ketua masyarakat yang yang bergelar Orang Tua Kampung pada masa itu. Ketua masyarakat tersebut terdiri daripada dua golon
gan kaum yang terdapat di kampung ini, iaitu satu kaum masyarakat keturunan Kedayan dan satu kaum masyarakat keturunan Bisaya. Ketua masyarakat kaum Kedayan ialah Orang Tua Bagul bin Laut dan dari keturunan Bisaya p**a Orang Tua Siman bin Uda. Dua orang ketua inilah yang telah bergabung tenaga berusaha meminta kepada Pihak Jabatan Pelajaran supaya mendirikan bangunan sekolah di Kampung Melikai. Dua orang ketua tersebut sedar betapa perlunya pelajaran kepada anak cucu mereka dan anak-anak buah di kampung Melikai. Maka mereka mendesak kepada Jabatan Pelajaran Sabah supaya mendirikan bangunan sekolah disebabkan keadaan anak-anak buah mereka di kampung ini sangat jauh ketinggalan dari segi bidang pelajaran, disebabkan semuanya buta huruf. Dalam tahun yang sama atas tindakan ketua-ketua tersebut, matlamat mereka telah dicapai. Maka Jabatan Pelajaran pun mendirikan sebuah bangunan yang diperbuat daripada kayu beratapkan zink berdinding papan separuh dinding berlantaikan simen yang berukuran 30 x 20 kaki dibina oleh Majlis Daerah Kuala Penyu. Bangunan rumah guru belum ada lagi. Dua orang pelatih telah ditugaskan mengajar. Abd Hassan bin Mohamad memangku sebagai Guru Besar dan En. Ag Damit bin Mohd Noor sebagai guru penolong. Oleh kerana bangunan rumah guru belum didirikan, guru-guru tersebut terpaksa tinggal di bangunan pondok yang dibuat secara gotong royong oleh penduduk kampung. Bilangan murid yang didaftarkan sebagai penuntut pertama pada masa itu ialah seramai 57 orang. Murid-murid tersebut datangnya dari Kampung Peringan, Kampung Manggis, Kampung Sarap, Kampung Siampak dan Kampung Melikai. Pada masa tersebut belum ada kemudahan yang dibina oleh kerajaan seperti jalanraya dan lain-lain keperluan asas untuk kemudahan Kampung Melikai dan sekitarnya. Cara murid-murid datang ke sekolah pada masa itu ialah ada yang pakai perahu dan ada yang berjalan kaki melalui hutan dan bukit bukau. Setahun demi setahun S.K Melikai semakin berkembang. Ini disebabkan atas kesedaran penduduknya yang tidak mahu ketinggalan dalam bidang pelajaran demi untuk kebaikan anak-anak mereka. Maka bangunan sekolah pun semakin bertambah bagi menampung bangunan sedia ada dan bangunan rumah guru p**a dibina untuk menempatkan tenaga pengajar yang bertambah setahun demi setahun dan guru besar pun bertukar ganti untuk memajukan S.K Melikai. Dengan kesungguhan dan semangat yang gigih, murid yang belajar di sekolah ini telah berjaya melanjutkan pelajaran ke peringkat sekolah menengah dan ada yang menjadi guru dan telah memegang jawatan di pelbagai jabatan hasil dari usaha mereka belajar di sekolah ini. Dari sejak tahun 1967 sehingga tahun 1985 banyak bangunan sekolah dan rumah guru telah didirikan oleh Jabatan Pelajaran. Bangunan rumah guru telah siap didirikan sebanyak 4 buah rumah yang mana diperbuat daripada tiang simen, berlantaikan papan dan berdindingkan papan juga beratapkan zink. Bangunan sekolah ini mempunyai 4 blok yang mana 2 daripadanya mengandungi 1 bilik bagi tiap-tiap sebuah dan 2 buah blok mengandungi 2 bilik setiap satu. Dalam tahun 1987, sebuah bangunan sekolah telah dirobohkan yang mana mengandungi 2 buah bilik kerna bangunan ini sudah tidak berfungsi lagi. Kemudian dibangunkan lagi sebuah bangunan untuk menggantikan bangunan yang telah dirobohkan itu. Bangunan yang baru itu mengandungi 3 buah bilik darjah dan jumlah bangunan yang terdapat di SK Melikai dari sejak tahun 1967 hingga tahun 1988 ialah 4 buah bangunan rumah guru dan 4 buah bangunan sekolah. Pada tahun 2003, Jabatan Pelajaran membina lagi 2 buah bangunan sekolah, sebuah bangunan mengandungi 4 bilik darjah dan sebuah bangunan mengandungi 2 bilik darjah. Manakala 1 buah bangunan rumah ( 2 unit ) guru juga dibina pada tahun yang sama.
