Asal mula terjadinya Nama Desa Tanjung Binga dikarenakan laut Desa Tanjung Binga merupakan tempat persinggahan dari Samudera Pasai (Malaka) ke Demak (Kerajaan Islam) yang mana pada zaman tersebut penduduk dipesisir pantai sudah memeluk Agama Islam. Menurut cerita tokoh masyarakat setempat sebelum penjajahan Kolonial Belanda, sudah ada beberapa keluarga yang tinggal dipesisir pantai yaitu salah satunya keluarga Kik Muhammad yang bermata pencaharian sebagai nelayan (Besiro), yang tempat bersironya berada didaerah Tanjung yang banyak siput (Bingak) sehingga mulai saat itu penduduk pesisir pantai menyebut daerah itu Tanjung Bingak (yang sekarang terletak antara Bukit Berahu dan Pulau Jemang).

Setelah Belanda masuk ke Pulau Belitung di daerah Tanjung Binga karena pantainya indah dan air bersih sering dikunjungi oleh menir-menir Belanda untuk mandi sehingga tempat itu disebut Kemandian Belandan (sampai saat ini tempat itu masih ada), jadi nama Tanjung Binga sudah ada sebelum Kolonial Belanda masuk ke Belitung dengan bukti berdirinya Mercusuar Lengkuas pada Tahun 1982 pada waktu menir Belanda sudah menyebut nama Desa Kami Desa Tanjung Bingak sampai saat ini.