Nama Desa Tengin Baru sendiri berasal dari nama sebuah sungai yang terletak di sebelah timur dan berlanjut ke sebelah selatan Desa. Nama sungai tersebut adalah sungai Tengin. Dengan harapan Sungai tersebut bisa menjadi salah satu sumber penghidupan bagi Warga Desa dan untuk tetap melestarikan nama Sungai Tengin. Maka pada rapat bersama antara warga Desa dan para Perangkat Desa pada tahun 1997 nama Desa Sepaku III resmi berganti nama menjadi Desa Tengin Baru.

Berdasarkan cerita orang tetua masyarakat menyatakan bahwa pada awalnya Desa Tengin Baru bernama Desa sepaku 3 pada saat datangnya warga transmigrasi pada tahun 1977, namun sebelumnya disebut Sepaku ini terdiri dari 2 (dua) Kelurahan, yaitu Kelurahan Mentawir dan Kelurahan Sepaku dengan batas awal di Patok 52 Desa Sepaku 2 yang sekarang menjadi Desa Sukaraja. Dan pada tahun 1977 itulah warga transmigrasi datang dari Pulau Jawa sebanyak 500 kepala keluarga sehingga meramaikan Daerah Sepaku dengan nama Desa Sepaku 3 dengan Kecamatan Balikpapan Seberang sehubung dengan perkembangan daerah dan pada Tahun bergabunglah dengan Kabupaten Pasir di Tanah Grogot sebagai Ibukota Kabupaten dengan nama Kecamatan Sepaku yang terdiri dari 11 Desa dan 4 Kelurahan.

Berdasarkan hasil musyawarah warga masyarakat dan para tokoh-tokoh yang ada di desa Sepaku 3 akhirnya Desa sepaku 3 Pada tahun 1998 menjadi Desa Tengin Baru yang mana di Desa tengin Baru banyak tinggal masyarakat adat Paser dan adanya sungai yang cukup besar bila kemarau sungai tersebut tidak kering di mana sungai yang membelah desa tersebut bernama Sungai tengin.