Bán đảo Malay đã phát triển thịnh vượng nhờ vị trí trung tâm của mình trên những con đường thương mại trên biển giữa Trung Quốc, Ấn Độ và Trung Đông. Ngay từ sớm, Ptolemy đã thể hiện trên tấm bản đồ của mình một dấu hiệu được dịch là Bán đảo vàng, Eo Malacca được gọi là Sinus Sabaricus. Từ giữa tới cuối thiên niên kỷ thứ nhất, đa số Bán đảo cũng như Quần đảo Malay nằm dưới tầm ảnh hưởng của Srivijaya.

Mọi người cho rằng ban đầu đây là những quốc gia Hindu hay Phật giáo. Bằng chứng đầu tiên của Hồi giáo trên bán đảo Malay có niên đại từ thế kỷ 14 tại Terengganu, nhưng theo Biên niên sử Kedah, Maharaja Derbar Raja thứ 9 của Vương quốc Hồi giáo Kedah đã cải sang đạo Hồi và đổi tên thành Quốc vương Hồi giáo Muzaffar Shah. Từ đó đã có 27 quốc vương Hồi giáo cai trị Kedah.

Có rất nhiều vương quốc Malay ở thế kỷ thứ 2 và 3, theo các nguồn thông tin Trung Quốc, con số này lên tới 30. Kedah cũng được gọi là Kedaram hay Kataha, trong tiếng Pallava hay tiếng Phạn cổ, được cai trị bởi Rajendra Chola, tới thế kỷ 11, dưới sự cai trị của vua Vir Rajendra Chola, tầm ảnh hưởng của Srivijaya, triều đình đã gây ảnh hưởng trên Kedah và Pattani và thậm chí tới cả Ligor, giảm sút.

Vương quốc Ligor Phật giáo chiếm quyền kiểm soát Kedah một thời gian ngắn sau đó, và vị vua của nó Chandrabhanu đã dùng nơi này làm căn cứ tấn công Sri Lanka ở thế kỷ 11, và thậm chí đã được nhắc tới trên một bản văn khắc đá tại Nagapattinum ở Tamil Nadu và trong biên niên sử Sri Lanka, Mahavamsa. Trong thiên niên kỷ đầu tiên, người dân trên bán đảo Malay đã chấp nhận Hindu giáo và Phật giáo và sử dụng ngôn ngữ tiếng Phạn cho tới khi họ cải theo Đạo Hồi, nhưng không trước khi Hindu giáo và Phật giáo và tiếng Phạn lẫn vào trong quan điểm về thế giới của người Malay. Những dấu vết về những ảnh hưởng trong các quan niệm chính trị, cơ cấu xã hội, nghi lễ, ngôn ngữ, nghệ thuật và văn hóa vẫn còn tồn tại cho đến ngày nay.

Có những thông tin về các vùng khác cổ hơn Kedah, ví dụ vương quốc cổ Ganganegara, quanh Bruas tại Perak, khiến lịch sử Malaysia thậm chí được kéo lùi xa hơn tới tận thời cổ đại. Nếu đó chưa đủ là bằng chứng, một bài thơ Tamil, Pattinapillai, ở thế kỷ thứ hai sau Công Nguyên, đã miêu tả những hàng hóa từ Kadaram tràn ngập trên những đường phố thủ đô Chola, một vở kịch tiếng Phạn thế kỷ thứ bảy là Kaumudhimahotsva, coi Kedah như Kataha-nagari. Agnipurana cũng đề cập tới một lãnh thổ được gọi là Anda-Kataha với một trong những biên giới được xác định bởi một đỉnh cao, mà các nhà sử học tin là Gunong Jerai. Những câu chuyện trong Katasaritasagaram miêu tả cuộc sống thanh lịch tại Kataha.

Đầu thế kỷ 15, Vương quốc Hồi giáo Malacca được thành lập dưới một triều đại do Parameswara, một hoàng tử từ Palembang với liên hệ huyết thống với hoàng gia Srivijaya, người đã phải bỏ chạy khỏi Temasek (Singapore hiện nay) sáng lập. Parameswara đã quyết định thành lập vương quốc của mình tại Malacca sau khi chứng kiến một tai nạn bất ngờ khi một chú nai trắng đá một trong những con chó săn của ông. Ông coi đó là một dấu hiệu may mắn và đặt tên cho vương quốc của mình là Melaka theo tên loài cây ông đang ngồi dưới nghỉ ngơi. Ở thời đỉnh cao, vương quốc hồi giáo đã kiểm soát nhiều vùng hiện là Bán đảo Malaysia, nam Thái Lan (Patani), và bờ biển phía đông Sumatra. Nó đã tồn tại trong hơn một thế kỷ, và khoảng thời gian này chính là lúc Đạo Hồi lan tràn ra hầu hết Quần đảo Malay.Malacca là cảng thương mại tiền đồn thời ấy tại Đông Nam Á.

Năm 1511, Malacca bị người Bồ Đào Nha chinh phục, và họ đã lập ra một thuộc địa ở đó. Những người con trai của vị quốc vương Hồi giáo cuối cùng của Malacca đã thành lập nên những vương quốc Hồi giáo ở nhiều địa điểm khác trên bán đảo. Vương quốc Hồi giáo Perak ở phía bắc, và Vương quốc Hồi giáo Johor (ban đầu là sự tiếp nối của Vương quốc Hồi giáo Malacca) ở phía nam. Sau khi Malacca sụp đổ, ba bên chiến đấu giành quyền kiểm soát Eo Malacca: người Bồ Đào Nha (tại Malacca), Vương quốc Hồi giáo Johor, và Vương quốc Hồi giáo Aceh. Cuộc xung đột này kéo dài đến tận năm 1641, khi người Hà Lan (liên minh với Vương quốc Hồi giáo Johor) giành quyền kiểm soát Malacca.

Anh Quốc đã thành lập thuộc địa đầu tiên của mình tại bán đảo Malay năm 1786, với việc cho thuê đảo Penang cho Công ty Đông Ấn Anh của Quốc vương Hồi giáo Kedah. Năm 1824, người Anh nắm quyền kiểm soát Malacca sau Hiệp ước Anh-Hà Lan 1824 phân chia quần đảo Malaya giữa Anh và Hà Lan, Malaya thuộc vùng của Anh. Năm 1826, Anh Quốc lập thuộc địa chưa độc lập (crown colony) Straits Settlements, thống nhất ba vùng thuộc sở hữu của họ tại Malaya: Penang, Malacca và Singapore. Straits Settlements nằm dưới quyền quản lý hành chính của Công ty Đông Ấn tại Calcutta cho tới năm 1867, khi quyền này được chuyển giao cho Văn phòng Thuộc địa tại London.

Cuối thế kỷ 19, nhiều bang Malay đã quyết định nhờ sự giúp đỡ của Anh để giải quyết các cuộc xung đột nội bộ của họ. Tầm quan trọng trong thương mại của ngành mở thiếc tại các bang Malay với các thương gia tại Straits Settlements khiến chính phủ Anh phải can thiệp vào các bang sản xuất thiếc trên Bán đảo Malay. Chính sách ngoại giao thuyền chiến của Anh được áp dụng để mang lại giải pháp hòa bình cho sự bất ổn do những tên cướp Trung Hoa gây ra, và Hiệp ước Pangkor năm 1874 đã mở đường cho sự mở rộng ảnh hưởng Anh tại Malaya. Tới đầu thế kỷ 20, các bang Pahang, Selangor, Perak, và Negeri Sembilan, được gọi chung là Liên minh các Bang Malay (không nên nhầm với Liên bang Malaya), trên thực tế nằm dưới quyền điều khiển của các Toàn quyền được chỉ định để cố vấn cho các vị vua cai trị Malay. Trên danh nghĩa người Anh chỉ là cố vấn, nhưng trên thực tế họ có ảnh hưởng mang tính quyết định với mọi vị vua cai trị Malay.

Năm bang còn lại trên Bán đảo Malay, được gọi là Các bang Malay không Liên minh, tuy không trực tiếp nằm dưới quyền quản lý của London, cũng đã chấp nhận các cố vấn Anh ở đầu thế kỷ 20. Trong số họ, bốn bang phía bắc là Perlis, Kedah, Kelantan và Terengganu từng nằm dưới tầm ảnh hưởng của Xiêm trước kia.

Trên đảo Borneo, Sabah được cai quản như thuộc địa chưa độc lập British North Borneo, tuy Sarawak đã được Brunei chấp nhận là một vương quốc riêng của gia đỉnh Brooke, những người cai trị như những Rajahs Trắng.

Sau khi người Nhật chiếm Malaya) trong Chiến tranh thế giới thứ hai, sự ủng hộ của dân chúng cho một nền độc lập ngày càng tăng.Những kế hoạch hậu chiến của Anh nhằm thống nhất quản lý hành chính Malaya dưới một thuộc địa duy nhất được gọi là Liên minh Malaya hình thành trong sự phản đối mạnh mẽ từ người Malay, họ phản đối sự nhu nhược của tầng lớp cai trị Malay và việc trao quyền công dân cho những người Trung Quốc. Liên minh Malaya, được thành lập năm 1946 và gồm tất cả các vùng đất thuộc quyền quản lý của Anh tại Malaya ngoại trừ Singapore, đã giải tán năm 1948 và bị thay thế bởi Liên bang Malaya, giữ lại quyền tự trị của những vị vua cai trị các bang Malay dưới sự bảo hộ của Anh.

Trong thời gian này, những người nổi dậy dưới sự lãnh đạo của Đảng cộng sản Malaya đã tung ra các cuộc tấn công du kích nhằm đẩy lực lượng Anh khỏi Malaya. Tình trạng khẩn cấp Malaya, như nó từng được gọi, kéo dài từ 1948 tới 1960, và dẫn tới một chiến dịch chống nổi dậy kéo dài của quân đội Khối thịnh vượng chung Anh ở Malaya.Chống lại tình hình này, nền độc lập cho liên minh trong Khối thịnh vượng chung đã được trao ngày 31 tháng 8 năm 1957.

Năm 1963 Liên bang được đổi tên thành Malaysia với sự chấp nhận của các thuộc địa khi ấy của Anh là Singapore, Sabah (British North Borneo) và Sarawak. Vương quốc Hồi giáo Brunei, dù ban đầu thể hiện ý muốn gia nhập Liên bang, đã rút khỏi kế hoạch hợp nhất vì sự chống đối từ một số phe phái nhân dân cũng như những tranh cãi về việc chi trả các khoản đặc lợi dầu mỏ và vị thế Vương quốc Hồi giáo của kế hoạch hợp nhất.

Buổi đầu độc lập đã gặp trở ngại bởi cuộc xung đột với Indonesia (Konfrontasi) về việc thành lập Malaysia, sự rút lui năm 1965 của Singapore và cuộc tranh giành sắc tộc dưới hình thức những cuộc bạo loạn sắc tộc năm 1969.Philippines cũng đưa ra tuyên bố chủ quyền với Sabah trong giai đoạn đó vì Vương quốc Hồi giáo Brunei nhượng lại những lãnh thổ đông bắc của họ cho Vương quốc Hồi giáo Sulu năm 1704. Tranh cãi lãnh thổ này vẫn đang tiếp diễn. Sau những vụ bạo loạn sắc tộc ngày 13 tháng 5 năm 1969, Chính sách Kinh tế Mới gây nhiều tranh cãi – được dự định làm gia tăng phần sở hữu trong nền kinh tế của các bumiputra ("người bản xứ", gồm cả cộng đồng người Malay đa số, nhưng không phải luôn là người bản xứ) đối lập với các nhóm sắc tộc khác - được Thủ tướng Tun Abdul Razak đưa ra . Từ đó Malaysia đã duy trì một sự cân bằng sắc tộc-chính trị mong manh, với một hệ thống chính phủ nỗ lực tổng hợp các lợi ích phát triển kinh tế với chính trị và các chính sách kinh tế dành ưu tiên cho Bumiputra.

Trong khoảng thập niên 1980 và giữa thập niên 1990, Malaysia trải qua thời kỳ tăng trưởng kinh tế đáng kinh ngạc với Thủ tướng Tun Dr Mahathir bin Mohamad.[19] Giai đoạn này cũng là sự chuyển đổi từ nền kinh tế dựa trên nông nghiệp sang chế tạo và công nghiệp trong những khu vực như máy tính và hàng điện tử tiêu dùng. Cũng ở thời gian này, bộ mặt Malaysia đã thay đổi với sự xuất hiện của nhiều dự án lớn. Đáng chú ý nhất là những dự án như Tháp đôi Petronas (khi ấy là toà nhà cao nhất thế giới), Sân bay Quốc tế KL (KLIA), Đường cao tốc Bắc-Nam, Đường đua F-1 Sepang, Siêu Hành lang Truyền thông (MSC), đập thuỷ điện Bakun và Putrajaya, một thủ đô hành chính liên bang mới.

Cuối thập niên 1990, Malaysia rung động bởi cuộc Khủng hoảng tài chính Châu Á cũng như tình trạng chính trị bất ổn do việc sa thải phó thủ tướng Dato' Seri Anwar Ibrahim.[20] Năm 2003, Tiến sĩ Mahathir, thủ tướng có thời gian cầm quyền dài nhất tại Malaysia về hưu, nhường chỗ cho phó thủ tướng Abdullah Badawi.