Dalam sejarah melayu disebutkan, di Tanjung Bemban inilah Sang Nila Utama atau Sri Tri Buana pernah berburu pelanduk. Sri Buana Utama adalah pendiri Kerajaan Melayu Singapura. Berdasarkan tuturan lisan, asal usul Kampung Tanjung Bemban tak bias dipisahkan dari legenda yang dituturkan oleh orang-orang Melayu yang telah lama bermastautin di pulau Batam. Dikisahkan bahwa, Tanjung Bemban dahulu kala hanya dihuni oleh beberapa orang penduduk. Diantara mereka, hiduplah sepasang suami istri yang memiliki seorang anak laki-laki yang telah beranjak dewasa. Singkat cerita, sang anak pergi merantau lalu berhaasil menjadi orang besar.
Sang ibu sangat berharap anaknya bias segera kembali dari perantauan. Setiap hari ia duduk disebuah batu ditepi pantai, menunggu kalau-kalau perahu anaknya merapat. Penantiannya tak sia-sia, pada hari yang ditunggu- tunggu, perahu sang anak pun tiba. Namun malang, sang anak ternyata tidak mengakui ibunya sebagai ibu. Murka , sang ibu menyumpahi sang anak sibiran tulangnya. Seketika itu juga sang anak beserta perahunya berubah menjadi batu. Batu itu kemudian dikenal dengan sebutan Malang orang, posisinya tepat di tepi pantai antara jabi dan Tanjung buton.
Sejak peristiwa itu,, nama Tanjugn Bemban menjadi sebutan ramai oleh orang-orang di pesisir Timur pulau Batam. Pasca Indonesia merdeka, banyak warga tanjung Bemban yang hijrah ke kampong yang letaknya berhampiran, yakni Batu Besar. Disana, mereka membaur dengan warga yang lebih dulu menetap dan mengandalkan hidup dari berkebun kelapa. Penamaan Bemban sendiri berasal dari kata beremban, yakni nama sejenis pohon yang tumbuh di kampong tersebut.
Sumber : Buku Nong Isa ( Tonggak awal Pemerintahan Batam)