Situé au sud-ouest de la péninsule malaisienne, bordé par celui de Johor et face au détroit de Malacca, le sultanat aurait été créé vers 1402 par Parameswara, prince hindouiste de Palembang dans le sud de Sumatra. Il s'est converti à l'Islam (à la fin de sa vie). Ses deux successeurs feront de même. Continuatrice des anciens royaumes de Temasek (ancien nom de Singapour) , Srivijaya et Palembang, La principauté était un carrefour des nations ( 84 selon le voyageur herboriste portugais Tomé Pires, qui y a séjourné deux ans) et du commerce maritime. La ville est particulièrement bien située, dans le sud de la péninsule, face au détroit avec Sumatra derrière. Le territoire du Sultanat était bien plus grand qu'actuellement, s'étendant sur la cote est de Sumatra, de l'autre coté du détroit. Au Nord, une partie de l'actuelle Thailande était sous sa coupe. Malacca s'est mis, sans doute pour se protéger du royaume siamois d'Ayutara , sous la protection de l'empereur de Chine. Huit sultans ont régné sur Malacca.
En 1509 arrivent les premiers portugais, qui ont déjà colonisé Goa, débarquent à Malacca. Il s'agit d'une mission mandatée par le roi du portugal Manuel le Grand et dirigée par Diego Lopes de Sequeira. Plusieurs portugais sont emprisonnés à Malacca déclenchant l'arrivée en renfort d'une seconde flotte en 1511.
Celle-ci composée de quinze à trente bateaux et mille deux cents hommes est commnandée par le vice-roi Affonso de Albuquerque. Il s'agit au départ de demander l'élargissement des prisonniers et d'obtenir la permission d'élever un fort près de la ville, ce qui est bien sur refusé par le Sultan. Les négociations échouent donc. Les portugais, qui souhaitaient surement s'emparer de cet emplacement stratégique, attaquent donc et en 12 jours font tomber la ville, qu'ils pillent pendant trois jours.
Le 20 aout 1511 , la ville est prise par les portugais, leur ouvrant un point d'entrée vers l'Asie. Les sultanats de Pahang, Perak et Johor ont eu pour sultan des descendants de la famille royale de Malacca après le départ de Mahmud Shah, dernier Sultan de de Malacca. La ville sera occupée ensuite par les hollandais, les anglais avant l'indépendance de 1957.
Ils chassent le dernier sultan Mahmud Shah qui va fonder Johor au sud en 1518. Malgré diverses tentatives, jusqu'en 1629, la ville ne sera pas reprise par le sultan ou un de ses successeurs.
Les portugais ayant le lieu mais non l'intégration au commerce local, ne sauront pas empêcher le déclin de la ville suite à leur conquête.
Les hollandais intéressés par Malacca (et alliés évidemment au sultanat de Johor) tentent aussi de prendre la ville, et réussiront à la cinquième tentative, après six mois de siège, à avoir raison des forces portugaises en 1641. Les Anglais s'empareront de la ville à leur tour en 1795, à la demande de Guillaume V d'Orange-Nassau, pour éviter que les Français victorieux des provinces-unies ne la prennent.
