Di Malaya perubahan Zaman Paleolitik (Zaman Batu Awal) hingga Zaman Batu Baru (peradaban) berlaku dalam dua peringkat dengan adanya pertembungan dari luar. Pertama, bangsa manusia yg mengembara ke selatan dari utara. Mereka tinggal di Semenanjung Tanah Melayu untuk beberapa ribu tahun. Mereka dianggap sebagai nenek moyang orang2 Melanesia di Pasifik, di mana mereka kemudiannya berpindah. Mereka juga dikenali sebagai orang2 Hoabinhian (satu nama tempat di Indo-China) dan tinggal dalam gua, menjadi pemburu yg cekap dan cara hidup yg lebih maju.
Orang Mesolitik ini hidup di gua kerana keadaan masih sejuk. Antara tempatnya di Bkt Chuping (Perlis), Kedah, 4 buah gua (Perak), 2 (Kelantan) dan 3 (Pahang). Hampir 8,000 tahun kemudian (tahun 2000 sebelum Masehi), mereka meninggalkan gua dan berpindah. Nenek moyang orang2 Melayu moden telah datang dari utara (Zaman Batu Baru atau Zaman Neolitik) dan menghalau atau mengahwini gadis2 mereka. Dari sinilah peradaban mulai berkembang dengan kedatangan mubaligh dan pedagang India, Arab, China dsbnya.
Penyelidikan ke dalam sejarah Asia Tenggara sebelum kedatangan Islam telah bermula dengan Henri Mouhot pada 1860. Sejumlah besar daripada tulisan2 sejarah sekarang adalah didasarkan pada penemuan itu. Pada 1918 terbukti satu empayar besar bernama SriVijaya (yg mana Malaya termasuk sebahagiannya) telah wujud, tetapi kita masih mencari ibu negaranya. Punca-punca dari Negara China ada menyebutkan tentang suatu negeri besar di Malaya bernama Langkasuka yg hidup selama 1000 tahun, dan Ptolemy menceritakan berkenaan suatu pelabuhan yg besar di Semenanjung Tanah Melayu atau di Semenanjung Kra yg bernama Takola. Satupun daripada kedua-dua tempat ini belum dijumpai lagi.