As origens precisas do Sultanato de Malaca são controversas. Ao que parece, foi fundada por Parameswara, um príncipe proveniente de Palimbão, em Serivijaia (um reino malaio em Samatra), que fugiu de Samatra em seguida a um ataque majapaíta em 1377. Ao chegar a Malaca em cerca de 1400, encontrou um bom porto, acessível em todas as estações e, do ponto de vista estratégico, num dos pontos mais estreitos do Estreito de Malaca.[1]
Segundo uma lenda popular, Parameswara descansava sob uma árvore próximo a um rio, quando caçava, quando um cervo-rato empurrou um de seus cães de caça rio adentro. Impressionado com a coragem do animal e com o que considerou um bom presságio, Parameswara teria decidido fundar ali um império, chamando-o Melaka, nome da árvore sob a qual ele se havia abrigado.Ver Etimologia e uso Parameswara converteu-se ao islã em 1414 e passou a chamar-se Sultão Iscandar Xá.
Com a colaboração dos povos do mar (orang laut) - corsários proto-malaios dos Estreitos, Parameswara fez de Malaca um grande porto internacional, ao compelir os navios de passagem a aportar ali e ao estabelecer instalações confiáveis e justas para depósito e comércio.[1] O Sultão Iscandar Xá faleceu em 1424, sucedendo-lhe seu filho.
A prosperidade de Malaca atraiu a invasão dos siameses. Entretanto, os ataques de 1446 e 1456 foram repelidas por Tun Perak. O desenvolvimento de relações entre Malaca e a China foi uma decisão estratégica para prevenir outros ataques siameses.
Devido a sua localização estratégica, Malaca foi um posto avançado importante da frota de Jeng He. Levou consigo Hang Li Po, alegadamente uma princesa chinesa do imperador Mingue, para casar-se com o Sultão Almançor Xá. Os 500 serviçais que a acompanharam casaram-se com os habitantes locais e assentaram-se em Bukit Cina.
No seu auge, Malaca era um sultanato poderoso que controlava o sul da Península Malaia e grande parte de Samatra. Sua presença impediu o avanço dos siameses na direção sul e possivelmente acelerou o declínio de seu rival, o Império Majapahita de Java. Malaca também desempenhou um papel-chave na disseminação do Islamismo no Arquipélago Malaio.
Em abril de 1511, Afonso de Albuquerque conquistou Malaca, que se tornou uma importante base para as operações portuguesas no Extremo Oriente.