Penamaan desa oleh Orang Punan biasanya mengikuti nama aliran sungai yang mereka diami. Seperti halnya Long Nyau yaitu kelompok masyarakat yang bermukim di sekitar Sungai Nyau . Namun tidak selalu masyarakat di Desa Long Nyau bermukim di area Sungai Nyau. Pada awalnya Long Nyau terdiri dari sebuah kelompok Punan Tubu yang tinggal di dearah Mabau, dalam sejarah Desa Long Nyau mereka dikenal sebagi orang-orang Long Mabau. Pada abad ke-18 terjadi pernikahan antara seorang laki-laki Punan Malinau dengan anggota dari Long Mabau. Pernikahan ini menyebabkan adanya terbaginya orang-orang Long Mabau menjadi dua, kelompok baru yang menetap di daerah Upa’ disebut dengan Long Upa’ dan Long Mabau yang memilih untuk menetap di dearah Mabau. Long Upa dan Long Mabau menjadi tulang belakang dari apa yang kini dikenal dengan Long Nyau.

Perubahan dari kehidupan nomaden menjadi sedenter memerlukan waktu yang lama sampai terbentuk desa yang kita kenal sekarang. Sejarah awal kehidupan sedenter muncul ketika pada masa pendudukan Jepang dari 1942-1945 masyarakat Long Upa dan Long Mabau dipaksa untuk menetap, namun tidak sepenuhnya perubahaan ini terimplementasikan. Kedua masyarakat tersebut masih melanjutkan kehidupan nomadennya. Peralihan dari kehidupan nomaden menjadi sedenter baru terlihat pada 1970-an pada periode awal kemerdakaan.

Pada masa pemerintahan Presiden Soekarno, kedua kelompok ini diminta untuk menetap oleh pemerintah. Seruan menetap diterima cukup baik oleh masyarakat Long Upa, namun Long Mabau tidak menghiraukan seruan tersebut dan tetap melakukan muvut. Namun kegiatan nomaden Long Mabau tidak berlangsung lama, seruan menetap oleh pemerintah juga disertakan oleh sebuah sumpah yang berbunyi “Jika orang-orang Mabau masih berpindah-pindah maka mereka akan mati” masyarakat Long Mabau pada saat itu tetap melakukan muvut dan sesuai sumpah dari pemerintah malapetaka menyusul orang-orang Long Mabau. Masyarakat Long Mabau yang bernomaden satu persatu meninggal dikarenakan penyakit. Mereka terus berpindah dari satu tempat ke tempat lainnya dengan harapan dapat menghindar dari penyakit dan malpetaka. Hingga anggota Long Mabau terlalu sedikit untuk melanjutkan kehidupan nomaden mereka. Anggota yang tersisa bergabung dengan Long Upa dan akhirnya menetap di Sungai Nyau, melahirkan nama desa yang kini dikenal dengan desa Long Nyau.

Saat ini masyarakat Long Nyau tidak lagi tinggal di sekitar Sungai Nyau namun bergeser ke Hulu Sungai Tubu di sekitar sungai Tepuh. Perpindahan tersebut bermula ketika 11 desa lainnya yang berada di Sungai Tubu pindah ke Malinau melalui program Respen (resettlement penduduk) dan melebur menjadi satu desa yaitu Desa Respen Tubu. Selain 11 desa yang pindah ke Malinau tersebut masih terdapat 5 desa lainnya yang memilih bertahan di tanah leluhurnya di hulu Sungai Tubu yaitu Desa Long Nyau, Long Ranau, Long Pada, Rian Tubu, dan Long Titi.

Masyarakat Long Nyau sendiri memilih untuk bertahan karena percaya bahwa Malinau pasti akan maju serta berkembang, dan pembangunan tersebut lambat laun akan menyentuh desa-desa yang berada di hulu, sehingga hanya perlu menunggu waktu tanpa perlu pindah ke tanah orang lain. Keyakinan tersebut mereka pegang teguh tanpa memperdulikan iming-iming akses pendidikan dan kesehatan yang lebih baik di kota.

Pada masa pemindahan 11 desa ke Malinau, 5 desa yang bertahan juga memiliki pemikiran untuk bergabung di satu lokasi yang sama. Keinginan tersebut didukung penuh oleh LAB-PKM (Lembaga Adat Besar Punan Kabupaten Malinau), sayangnya Long Titi dan Rian Tubu tidak ingin ikut bergabung dan memilih untuk menetap di desanya. Desa yang sepakat untuk bergabung diantaranya Long Pada, Long Ranau, dan Long Nyau. Lokasi yang saat itu disepakati untuk bermukim bersama ialah Long Tepuh, yaitu sebuah dataran luas di dalam wilayah Desa Long Nyau.

Sayangnya, kesepakatan tiga desa tersebut tidak sepenuhnya diterima oleh masyarakat, terdata saat itu sebagian masyarakat Long Pada dan Long Ranau masih bertahan di desanya masing-masing karena enggan bergabung di Long Tepuh dan ingin mempertahankan tanah desanya. Sementara itu, Masyarakat Long Nyau seluruhnya pindah ke Long Tepuh karena 2 alasan, yang pertama karena Long Tepuh masih merupakan wilayah desa Long Nyau dan yang kedua karena pemukiman Long Nyau di muara Sungai Nyau sering terendam oleh banjir dari Sungai Tubu yang meluap.

Dasar pemikiran untuk meleburkan 3 desa yang berada di Sungai Tubu ke satu lokasi yang sama ialah karena para pemimpin desa menganggap akses dari Kota menuju lokasi pemukiman mereka tidaklah mudah. Sehingga mereka perlu mempermudah jangkauan pemerintah dengan cara bergabung pada satu lokasi yang mudah untuk diakses. Alasan lainnya, terdapat isu bahwa Sungai Tubu akan dimekarkan menjadi Kecamatan sendiri, yaitu Kecamatan Sungai Tubu. Pemilihan Long Tepuh sebagai tempat untuk bermukim tidak terlepas dari morfologi lahan yang cenderung datar, imajinasi masyarakat saat itu jika mereka telah bermukim di satu tempat dan telah menjadi satu kecamatan maka akan mudah untuk membangun landasan pesawat terbang, bahkan masyarakat telah menyurvei 2 lokasi calon landasan yang memungkinkan di sekitar Long Tepuh. Setelah Long Pada dan Long Ranau kembali ke kampungnya, Desa Long Nyau memutuskan untuk tetap di Long Tepuh karena seluruh masyarakatnya telah membuat rumah di sana. Beberapa diantara mereka telah membuat rumah permanen dengan lembar-lembar papan dan atap seng bahkan terdapat pula masyarakat yang membongkar dan membawa bahan bangunannya dari Long Nyau ke Long Tepuh.

Setelah masuknya program GERDEMA (Gerakan Desa Membangun) kemudian status Sungai tubu menjadi kecamatan perwakilan/pembantu, namun ibu kotanya tidak di Long Tepuh melainkan Long Pada. Program GERDEMA yang mengalokasikan APBD untuk pembangunan desa merupakan alasan utama Long Pada dan Long Ranau kembali ke kampungnya. Mereka beranggapan bahwa setelah adanya anggaran GERDEMA di tiap desa maka akan lebih baik jika membangun desa masing-masing.