Hồi giáo truyền đến quần đảo Mã Lai thông qua những thương nhân Ả Rập và Ấn Độ trong thế kỷ 13, kết thúc thời kỳ của Ấn Độ giáo và Phật giáo. Hồi giáo dần tiến đến khu vực, và trở thành tôn giáo của tầng lớp ưu tú trước khi truyền bá đến thường dân. Hồi giáo tại Malaysia chịu ảnh hưởng từ các tôn giáo trước đó và nguyên bản là không chính thống.Cảng Malacca trên bờ biển phía tây của bán đảo Mã Lai được thành lập vào năm 1402 theo lệnh của Parameswara, một hoàng tử của Srivijaya tẩu thoát khỏi Temasek (nay là Singapore). Sau khi tẩu thoát, Parameswara tiến về phía bắc để thành lập một khu định cư. Tại Muar, Parameswara cân nhắc đặt quốc gia mới của mình tại Biawak Busuk hoặc là Kota Buruk. Nhận thấy vị trí của Muar không phù hợp, ông tiếp tục đi về phía bắc. Ông tiến đến một làng cá tại cửa sông Bertam (tên cũ của sông Melaka), và thành lập khu định cư mà sau phát triển thành Vương quốc Malacca. Theo Biên niên sử Mã Lai, tại đây Parameswara trông thấy một con cheo cheo đá một con chó nghỉ bên dưới một cây Malacca, ông cho rằng đây là một điềm lành nên quyết định kiến lập một vương quốc mang tên Malacca. Ông cho xây dựng và cải tiến hạ tầng cho mậu dịch, Vương quốc Malacca thường được nhìn nhận là quốc gia độc lập đầu tiên tại bán đảo.Thời điểm Malacca hình thành, hoàng đế triều Minh phái các hạm đội đi khuếch trương mậu dịch. Đô đốc Trịnh Hòa ghé thăm Malacca và đưa Parameswara cùng mình trở tại Đại Minh, một sự công nhận vị thế quân chủ hợp pháp của ông. Đổi lại việc được triều cống thường lệ, hoàng đế Đại Minh cung cấp sự bảo hộ cho Malacca trước đe dọa liên tục về một cuộc tấn công của Xiêm. Người Hoa và người Ấn định cư tại bán đảo mã Lai trước và trong giai đoạn này là tổ tiên của cộng đồng Baba-Nyonya và Chetti hiện nay. Theo một giả thuyết, Parameswara trở thành một người Hồi giáo khi ông kết hôn với một công chúa của Pasai và lấy tước hiệu Ba Tư là "Shah", tự xưn ... Tiếp tục ở trên, sao cho nó trả lời "国王自称为什么？":
g là Iskandar Shah. Biên niên sử Trung Hoa đề cập rằng vào năm Vĩnh Lạc thứ 9 (1414), con trai của quân chủ đầu tiên của Malacca đến chầu hoàng đế Đại Minh để thông báo rằng cha mình đã từ trần. Con trai của Parameswara sau đó được hoàng đế Đại Minh chính thức công nhận là quân chủ thứ nhì của Malacca, mang tước Raja Sri Rama Vikrama, và được các thần dân Hồi giáo biết đến với tước Sultan Sri Iskandar Zulkarnain Shah hay Sultan Megat Iskandar Shah. Ông cai trị Malacca từ năm 1414 đến năm 1424. Thông qua ảnh hưởng của những người Hồi giáo Ấn Độ, và ở một mức độ thấp hơn là người Hồi từ Trung Quốc, Hồi giáo trở nên ngày càng phổ biến trong thế kỷ 15.