Pulau Batam dahulunya bernama pulau batang, sebagaimana terdapat pada peta pelayaran VOC tahun 1675 yang masih tersimpan di Perpustakaan Universitas Leiden Belanda. Menurut sejarah, Batam pertamakali dihuni oleh orang laut/orang selat. Diperkirakan merekalah suku asli batam yang ber ras melayu. Orang selat ini menghuni batam pertama kali pada 231M yang disebut pulau ujung pada zaman singapura.
Nama batam yang berasal dari pulau Batang ini menurut legenda diambil karena hampir seluruh pantai batam yang menghadap ke laut cina selatan ditumbuhi batang pohon jenis tertentu yang khas. Pohon tersebut dibutuhkan oleh para pelaut dan sering singgahdi pulau batam untuk mengambilnya. Selain itu terdapat juga versi lain cerita nama pulau batam berasal dari “Batang” yang berarti “jembatan” atau “ jalur penghubung antar pulau Bintang (Bintan), Bulang (bulan), lingga, dan pulau-pulau lainnya ke temasik (singapura) dan johor.Versi lain ada yang menyebutkan dari nama perkampungan terawal di batam, yaitu “Batuampar” yang disingkat namanya menjadi “Batam”.
Nama Batam banyak disebut dalam catatan perjalanan bangsa asing dan dokumen sejarah, termasuk dalam Traktat London 1824 dan dokumen Kerajaan Riau-Lingga. Berdasarkan catatan China, Batam dan pulau sekitarnya sudah dihuni manusia sejak 231 M. sebagaimana Temasek (Singapura) yang pada masa itu masih disebut Pulau Ujung (karena berada diujung Tanah Semenanjung), pesisir Kepulauan Batam dihuni oleh Suku Laut atau disebut juga Orang Selat. Sedangkan didaratan (hutan belantara) dihuni suku pedalaman seperti Suku Sakai dan Suku Jakun.
Kawasan Kepulauan Riau dan Tanah Semenanjung, termasuk kepulauan Batam, pernah menjadi wilayah Kerajaan Melayu Singapura, Kemaharajaan Melayu Malaka, Kemaharajaan Melayu (Johor, Riau, Lingga, Pahang dan Seluruh Daerah Taklukannya) dan Kerajaan Riau-Lingga. Pada awal Kemaharajaan Melayu (pasca-runtuhnya Melaka), kepulauan Batam menjadi wilayah langlang laut (pengawalan) Hang Nadim. Lakasamana Melayu berkhidmat sejak masa Sultan Mahmud Syah I dan Sultan Alauddin Riayat Syah II itu diberikan amanah sebagai Raja Laut atau Langlang Laut yang bertanggung-jawab membendung pengaruh bangsa asing (terutama Portugis) di kepulauan Melayu.
Dan Kepulauan Melayu dimaksud termasuk Pulau Batam dan sekitarnya. Mengacu berbagai sumber, Edi Sutrisno dkk (Bercermin Sejarah Menyongsong Batam Masa Depan (2007) hlm. 3) menyebutkan, Penduduk Melayu yang bermukim di kepulauan Batam berasal dari Tanah Semenanjung Melayu (Malaysia dan Singapura sekarang) serta Jambi.
Sebagaimana diketahui,, seputar abad ke-17 M, pernah terjadi perang antara Johor dan Jambi dan tidak tertutup kemungkinan para tentaranya banyak yang kemudian tinggal dan menetap di kepulauan Melayu, termasuk kawasan Batam. Sementara pendapat yang mengatakan berasal dari Tanah Semenanjung Melayu tak terbantahkan lagi, karena kepulauan Batam berdepan-depan langsung dengan kawasan itu. Masih menurut Edi Sutrisno dkk Bercermin Sejarah Menyongsong Batam Masa Depan (2007) hlm. 4), dalam abad ke-17 M sudah ada penduduk yang mendiami kawasan pesisir Bukit Layang, terdiri dari Suku Sakai yang hidup dengan mencari minyak kayu, damar, dan rotan. Sedangkan pada 1790, penduduk asli bernama A’lama yang beristrikan orang Melayu, mebuka wilayah yang kemudian bernama kampong Setenga. Pada 1813 dibuka pula perkampungan kelak yang bernama Patam yang didiami orang Melayu dari Pahang.
Sementara itu, pada 1817 telah ditemui penduduk etnis China dikawasan Sei Panas. Etnis China juga banyak yang bermukim di kawasan lain di kepulauan Batam seperti Duriangkang, Mukakuning, dan Tanjunguncang, Waheng, dan sebagainya. Dan pada 1820 kawasan Teluk Lengong telah dihuni penduduk Melayu yang dipimpin Wak Gendut. Di masa Kerajaan Lingga-Riau atau Riau - Lingga (1819-1913), telah terjadi perpindahan besar-besaran orang Melayu ke Batam dan diantara mereka mebuka perkampungan yang kelak dikenal sebagai Nongsa, Tanjunguma, Tanjungpantun, Tanjungriau, Tanjungsengkuang, Telagapunggur, Tanjungbemban, Kampung Belian, Kampung Bagan, Labuan Garap, dan sebagainya. Yang berpindah dan membuka perkampungan di Batam tersebut umumnya kaum kerabat kerajaan.
Selain sebai nelayan, mereka juga menanam gambur dan lada (hitam). Seiring itu, orang China juga banyak yang dating ke Batam serta bekerja di lading-ladang gambir dan lada.ada juga yang berkebun karet dan durian. Kemudian banyak yang berdagang serta membuka usaha pelayaran. Banyak tokoh dalam korpus sejarah Melayu yang telag diabadikan menjadi nama tempat atau nama jalan di bekas wilayah Kemaharajaan Melayu, baik di Malaysia, Singapura, Brunei Darusslama, dan Indoensia, apalagi di Provinsi Kepulauan Riau dan Riau. Khusus di Kota Batam, pengabadian nama tokoh dalam sejarah Melayu dalam sejarah Melayu di antara yang terpenting dapat disenaraikan sebagai berikut ini;
Bandara Hang Nadim
Stadion Temenggung Abdul Jamal
Gedung Nong Isa
Bumi Perkemahan Raja Ali Kelana
Dataran Engku Putri
RS. Engku Embung Fatimah
sumber : dinas kebudayaan provinsi kepulauan riau