Nama Rembau diambil dari nama sejenis pokok yang bernama Merbau. Kisah bermula apabila sekumpulan orang asli terjumpa sebatang pokok Merbau yang amat besar dan tinggi menjulang. Pokok tersebut tumbuh di kaki Gunung Datok. Adapun Gunung Datok itu banyak menyimpan kisah sejarah dan kini orang ramai suka mendakinya sebagai salah satu aktiviti mendaki gunung.

Nama Rembau bermula dari peristiwa sekumpulan orang-orang asli yang diketuai oleh Batin Sekudai hendak membuat penempatan baru dikaki Gunung Datok. Semasa membuat kerja menebas dan menebang dalam usaha membersihkan kawasan tersebut mereka terjumpa sebatang pokok yang amat besar dan tinggi menjulang. Setelah bebincang akhirnya mereka membuat keputusan menebang pokok Merbau itu kerana kawasan tersebut hendak dijadikan tempat kediaman. Mereka bimbang pokok yang besar itu akan membahayakan keselamatan mereka.

Maka mereka pun menebang pokok Merbau tersebut secara bergilir-gilir dengan menggunakan kapak dan beliung. Mereka berkerja siang dan malam selama tujuh hari tujuh malam. Tetapi apa yang menghairankan mereka ialah pokok tersebut masih juga tidak mahu tumbang.

Setelah genap tujuh hari tujuh malam mereka berusaha untuk menumbangkan pokok Merbau tersebut tetapi masih tidak berjaya, akhirnya mereka mengadukan perkara itu kepada seorang Bomoh yang paling handal di kalangan mereka. Dan setelah bomoh itu melihat pokok tersebut maka bomoh itu menyuruh orang-orang asli itu mendaki Gunung Datok hingga sampai ke kemuncak. Kemudian mereka hendaklah meminta izin dari penunggu Gunung tersebut untuk menebang pokok Merbau tua itu.

Esoknya beberapa orang asli mendaki Gunung Datok dengan membawa pelbagai persembahan untuk diberikan kepada penunggu yang dipercayai berada di puncak gunung tersebut. Setelah sampai di puncak Gunung Datuk, mereka pun menyeru nama penunggu gunung itu sambil meminta kebenaran untuk menebang pokok Merbau tua yang tumbuh di kaki gunung itu. Setelah selesai mereka pun pulang ke rumah masing-masing.

Pada malamnya turunlah hujan lebat bersama ribut kencang. Dan pada keesokan paginya mereka beramai-ramai keluar dari rumah masing-masing menuju ke pokok Merbau tua itu untuk meneruskan kerja penebangan.

Tetapi alangkah terperanjatnya mereka bila melihat pokok Merbau tua yang amat besar dan tinggi itu sudah pun tumbang menyembah bumi. Mereka amat hairan melihat pangkal pokok yang begitu besar dan untuk mengukur lebarnya mereka duduk bersila di perdu pokok itu. Kabarnya setelah 40 orang duduk bersila barulah penuh pangkal pokok Merbau yang ditebang itu.

Mereka menjamu selera sambil bersuka ria menandakan sudah berjaya menumbangkan pokok yang paling besar itu. Sebahagian dari mereka menyusuri batang pokok itu untuk mencari pucuknya. Kabarnya pucuk pokok Merbau yang tumbang itu sampai ke sebuah sungai lalu Sungai itu dinamakan Sungai Ujung.

Dan kawasan pangkal pokok itu mereka namakan Kampung Merbau Tua. Untuk meringkaskan sebutan mereka sebut " Kampung Merbau" sahaja dan akhirnya bertukar menjadi Rembau sahaja. Menurut ceritanya, sekumpulan orang-orang Minangkabau yang datang dari Pagar Ruyung Sumatera Barat telah datang ke Rembau dengan tujuan mengembangkan agama Islam di samping berniaga.

Oleh kerana orang-orang asli disitu menyambut kedatangan mereka dengan baik lalu mereka mengambil keputusan untuk menetap di situ malah ramai yang berkahwin dengan penduduk tempatan. Datok Lela Balang iaitu ketua orang-orang Minangkabau telah membuka sebuah penempatan baru berhampiran kampung Merbau Tua dan kampung yang baru dibuka itu dinamakan kampung kota. Kampung tersebut masih ada hingga sekarang.

Adik Datok Lela Balang pula membuka sebuah penempatan lagi lalu dinamakan Kampung Padang Lekuk. Sejak itu semakin ramailah orang-orang Minangkabau datang ke Rembau dan orang-orang asli pula meninggalkan tempat itu untuk membuat penempatan baru.


Menurut ceritanya lagi, Raja Melewar dari Pagar Ruyung Minangkabau datang ke Negeri Sembilan melalui Sungai Rembau lalu bersemayam di Kampung Penajis, tidak jauh dari Kampung Kota. Kemudian baginda mendirikan sebuah istana lalu dinamakan Kampung Istana Raja.

Apabila istana itu terbakar maka didirikan sebuah istana baru di Seri Menanti. Dan hingga sekarang Yang Dipertuan Besar Negeri Sembilkan bersemayam di Istana Besar Seri Menanti.
Adapun nama-nama kampung seperti kampung Kota, kampung Penajis, kampung Istana Raja dan kampung Sawah Raja masih kekal namanya sehingga sekarang