Terdapat banyak kerajaan Tiongkok dan India pada abad ke-2 dan ke-3 Masehi—sebanyak 30 buah menurut sumber Tiongkok. Kedah—dikenal sebagai Kedaram, Cheh-Cha (menurut I-Ching), atau Kataha di dalam tulisan Palawa atau bahasa Sanskerta kuno—berada di jalur serbuan pedagang dan raja India.
Rajendra Chola, Kaisar Tamil kuno yang diduga berada di sekitar Kota Gelanggi, menjadikan Kedah tunduk pada 1025, tetapi penggantinya, Vira Rajendra Chola, harus melumpuhkan pemberontakan Kedah untuk mengatasi para penyerbu. Kedatangan Chola berhasil meredam keagungan Sriwijaya, yang memberi pengaruh besar kepada Kedah dan Pattani bahkan sampai ke Ligor.
Kerajaan Buddha, Ligor mengambil kendali Kedah segera setelahnya, dan rajanya, Chandrabhanu menggunakan tempat ini sebagai basis untuk menyerang Sri Lanka pada abad ke-11, sebuah peristiwa yang dipahat di atas prasasti batu di Nagapattinum di Tamil Nadu dan di dalam kisah-kisah bangsa Sri Lanka, Mahavamsa. Selama milenium pertama, masyarakat di Semenanjung Malaya mengadopsi Hindu dan Buddha dan penggunaan bahasa Sanskerta hingga mereka beralih kepada Islam.
Ada beberapa laporan dari wilayah lain yang lebih tua dari Kedah—misalnya kerajaan kuno Gangga Negara, di sekitar Beruas di Perak, mendorong sejarah Malaysia lebih jauh ke belakang. Jika itu belum cukup, sebuah puisi Tamil, Pattinapillai, dari abad ke-2 M, menjelaskan barang-barang dari Kadaram menumpuk di jalanan ibukota Chola. Sebuah drama sanskerta dari abad ke-7, Kaumudhimahotsva, merujuk Kedah sebagai Kataha-nagari. Agnipurana juga menyebutkan sebuah daerah yang dikenal Anda-Kataha dengan salah satu batasnya menggambarkan sebuah puncak gunung, yang diyakini para sarjana sebagai Gunung Jerai. Kisah-kisah dari Katasaritasagaram menjelaskan kemewahan hidup di Kataha.
Gedung Sultan Abdul Samad di Kuala Lumpur, kompleks Pengadilan Tinggi Malaysia dan Pengadilan Perdagangan. Kuala Lumpur adalah ibukota Negara-negara Melayu Bersekutu dan ibukota Malaysia saat ini.
Pada permulaan abad ke-15, Kesultanan Melaka didirikan di bawah sebuah dinasti yang didirikan oleh Parameswara, pangeran dari Palembang, Indonesia, di dalam kerajaan Sriwijaya. Penaklukan memaksa dia dan pendukungnya melarikan diri dari Palembang. Untuk menghindari penganiayaan, Parameswara berlayar ke Temasek demi mendapatkan perlindungan Temagi, seorang penghulu Melayu dari Pattani yang ditunjuk oleh Raja Siam sebagai bupati Temasek. Beberapa hari kemudian, Parameswara membunuh Temagi dan mengangkat dirinya sendiri sebagai bupati. Kira-kira lima tahun kemudian, dia meninggalkan Temasek karena ancaman dari Siam. Selama periode ini, Temasek juga diserang oleh serombongan armada Jawa dari Majapahit.
Dia kemudian memimpin ke utara untuk mendirikan permukiman baru. Di Muar, Parameswara berkehendak mendirikan kerajaan barunya di Biawak Busuk atau di Kota Buruk. Mengetahui lokasi Muar tidaklah cocok, dia meneruskan perjalanannya ke utara. Di sepanjang jalan, dia mengunjungi Sening Ujong (nama lama untuk Sungai Ujong modern) sebelum sampai di sebuah perkampungan nelayan di bibir Sungai Bertam (nama lama untuk Sungai Melaka modern). Tempat itu lambat laun berkembang menjadi lokasi Melaka masa kini.
Menurut Sejarah Melayu, di situlah dia menyaksikan kancil mengecoh anjing ketika berteduh di bawah pohon Melaka. Dia mengambil apa yang dia lihat sebagai pertanda yang baik dan kemudian dia mendirikan sebuah kerajaan yang disebut Melaka, kemudian dia membangun dan memperbaiki fasilitas untuk tujuan perdagangan.
Peralihan agama Parameswara ke Islam tidaklah jelas. Sabri Zain mengemukakan, Parameswara menjadi seorang Muslim ketika dia menikahi seorang Puteri Samudera Pasai dan menyertakan gelar bergaya Persia “Syah”, dengan menyebut dirinya Iskandar Syah . Juga ada referensi yang menunjukkan bahwa beberapa anggota kelas penguasa dan komunitas saudagar yang menetap di Melaka telah menjadi Muslim. Kisah-kisah Tiongkok menyebutkan bahwa pada 1414, putera penguasa pertama Melaka mengunjungi Ming untuk mengabari mereka bahwa ayahnya telah wafat.
Putera Parameswara diakui secara resmi sebagai penguasa kedua Melaka oleh Kaisar Tiongkok dan bergelar Raja Sri Rama Vikrama, Raja Parameswara dari Temasik dan Melaka dan dia dikenal sebagai tokoh Muslim Sultan Sri Iskandar Zulkarnain Syah atau Sultan Megat Iskandar Syah, dan dia menguasai Melaka dari 1414 sampai 1424. Kerajaan ini menguasai wilayah yang sekarang ini disebut Semenanjung Malaya, selatan Thailand (Pattani, dan pantai timur Sumatera. Kerajaan ini berlangsung selama lebih dari satu abad, dan dalam periode tersebut menyebarkan Islam ke seluruh Nusantara. Melaka, sebagai pelabuhan perdagangan penting, terletak hampir di tengah-tengah rute perdagangan Tiongkok dan India.
Pada 1511, Melaka ditaklukkan oleh Portugal, yang mendirikan sebuah koloni di sana; maka berakhirlah Kesultanan Melaka. Tetapi, Sultan terakhir melarikan diri ke Kampar, Riau, Sumatera dan meninggal di sana. Putera-putera Sultan Melaka terakhir mendirikan dua kesultanan di tempat lain di semenanjung & mdash; Kesultanan Perak di utara, dan Kesultanan Johor (mulanya kelanjutan kesultanan Melaka kuno) di selatan.
Setelah jatuhnya Melaka, tiga negara berjuang menguasai Selat Malaka: Portugis (di Melaka), Kesultanan Johor, dan Kesultanan Aceh. Konflik ini berlangsung sampai tahun 1641, ketika Belanda (bersekutu dengan Kesultanan Johor) untuk merebut Melaka.
Kerajaan ini merupakan kelanjutan dari Kesultanan Malaka tua, tapi sekarang dikenal dengan nama Kesultanan Johor, yang masih ada sampai sekarang. Setelah jatuhnya Melaka, tiga negara berebut untuk mengambil kontrol Selat Malaka: Portugis (di Malaka), Kesultanan Johor, dan Kesultanan Aceh; dan peperangan berakhir pada 1641, ketika Belanda (bersekutu dengan Kesultanan Johor) merebut Malaka.