Nunuyan Laut adalah sebuah pulau kecil yang terletak di pinggir Teluk berhadapan dengan Lapangan Terbang Sandakan.Pulau ini hanya boleh berhubung melalui jalan laut dengan menggunakan perahu , boat dan kapal.
Diawal tahu 50-an pulau ini di penuhi dengan pokok kelapa. Kebun kelapa inilah menjadi sumber pendapatan kepada setiap penduduk pulau ketika itu. Penduduk di pulau ini terdiri daripada suku kaum Banjar,Suluk dan Bajau. Jumlah penduduk pada ketika itu lebih kurang 350 orang.
Pada tahun 1955, Goverment Primary School Nunuyan Laut telah ditubuhkan atas daya usaha gigih seorang anak jati pulau ini. Beliau yang dikenali sebagai Allahyarham Dato Panglima Hj.Sabran Hj.Abul. Beliau bertanggungjawab ke atas pendidikan anak-anak di pulau ini pada masa itu.
Bangunan G.P.S Nunuyan Laut yang pertama telah didirikan pada tahun 1955 atas bantuan penjajah British. Bangunan sekolah ini pada ketika itu hanya mempunyai sebuah bilik darjah dan dua bilik stor. Bilangan murid pada ketika itu seramai 40 orang murid yang terdiri dari pelajar-pelajar pulau itu sendiri. Cikgu Awang Tuah B. Hashim ialah guru pertama yang mengajar di Sek.Nunuyan Laut pada ketika itu.
Pada tahun 1957, perkembangan sekolah telah menarik perhatian penduduk pulau-pulau berdekatan. Antaranya, Pulau Pamaguan dan Pulau Libaran. Bilangan pelajar semakin bertambah dari tahun ke tahun yang menyebabkan sekolah ini terpaksa mengadakan dua sidang pada pagi dan petang.
Pada tahun 1959, bekas bangunan G.P.S telah dipindahkan ke pulau ini untuk menambahkan bilangan bilik darjah menjadi 4.
Pada tahun 1960, sebuah lagi rumah guru telah didirikan(sekarang ini ia dijadikan bilik kelas pemulihan).
Dalam tahun 70an bilangan pelajar semakin bertambah di mana mereka ini adalah penduduk-penduduk yang datang dari Kampung Sebait, Kampung Tinosa dan juga Kampung Batu Tiga.
Pada tahun 1980 sebuah bangunan baru yang mengandungi 3 bilik darjah telah siap dibina di bawah kelolaan Jabatan Pelajaran Negeri dan Persekutuan. Bangunan baru ini adalah untuk menggantikan bangunan lama yang sudah usang.
Dari tahun 1980 hingga 1984 sekolah ini telah menggunakan bangunan baru dengan menjalankan dua sidang pengajaran dan pembelajaran.
Pada tahun 1985, sebuah lagi bangunan baru mengandungi tiga bilik darjah dan sebuah rumah guru berkembar telah dibina. Bangunan ini adalah Projek Kilat Kementerian Pelajaran ketika itu. Bangunan baru dan sekolah ini telah dirasmikan pembukaannya pada 01 Oktober 1985 oleh Timbalan Menteri Pelajaran, YB Hj.Bujang Ulis.
