הדעות חלוקות לגבי שנת הייסוד המדויקת. העיר עצמה חגגה את שנת ה-600 לייסודה באוגוסט 1990, כלומר על פי שלטונות העיר היא נוסדה ב-1390, אבל היסטוריונים שונים נוקבים בתאריכים שונים בין 1376 ל-1402, כשהשנה המקובלת ביותר היא 1396. גם מקור שם העיר שנוי במחלוקת. הסיפור המקובל על מקור שם העיר מתאר כיצד פרמסווארה נח מתחת לעץ במהלך מסע ציד וצפה בכלביו מנסים לתקוף איילון מלאי - מין יונק קטן - שהתגונן בפניהם בעוז. אומץ הלב שהראה האיילון הזכיר לנסיך את מצבו והוא החליט לקרוא למקום על שם העץ שתחתיו נח. העץ, אמבליקה שחורה ("Phyllanthus emblica"), קרוי במלאית "פוקוק מלאקה" (Pokok Melaka). מכאן שם העיר (שממנו נגזרו אחר כך שמות הנהר העובר בעיר, המדינה שבה היא נמצאת ומצר הים הסמוך).
היישוב החדש התפתח במהירות. אנשיו של פרמסווארה עיבדו את השדות שמסביב וגידלו בהם בננות, קני סוכר ובטטות. פרמסווארה טיפח את המסחר, ובתוך זמן קצר נפוצה השמועה בשווקים של דרום-מזרח אסיה והודו על נמל המסחר החדש. בתוך שנתיים מייסוד היישוב גדלה אוכלוסייתו ל-2,000 נפש. במקום התיישבו סינים, הודים, בורמזים, תושבים מג'אווה וממקומות אחרים. הידיעות על מרכז הסחר החדש הגיעו עד בייג'ינג בירת סין. ב-1405 ביקר במלאקה שליח מטעם קיסר סין. ביקורו אפשר לסוחרים סיניים להקים מחסנים בעיירה. שליח ששלח פרמסווארה לקיסר יונג לה, הקיסר השלישי משושלת מינג, חיזק את הקשרים עם האימפריה הסינית. יונג לה שלח עם השליח מכתב שבו הכיר רשמית בפרמסווארה כשליט מלאקה, ומלאקה הוכרה כמדינת חסות של סין. השליח חזר בצי של האדמירל ג'נג חה במסעו הראשון ב-1405. ג'נג חה עתיד היה לבקר במלאקה כמעט בכל שבעת מסעותיו הנודעים.
פרמסווארה נשא לאישה נסיכה מוסלמית מממלכת פסאי (Pasai) שבצפון סומטרה, וב-1409 התאסלם, והוסיף לעצמו את השם הפרסי "אסכנדר שאה" ואת התואר סולטאן. שנתיים אחר כך ביקר הסולטאן וכל משפחתו, בלוויית פמליה בת 540 איש, בסין על מנת לחלוק כבוד לקיסר יונג לה. פרמסווארה מת ב-1414.
את פרמסווארה ירש בנו, שכונה הסולטאן מגאט איסקנדר שאה (Megat Iskandar Syah; שלט 1414–1424). מלאקה המשיכה לשגשג תחת שלטונו. בדיל נתגלה בחלקה הצפוני של מלאקה, מהיערות שבסביבה הפיקו פחמי עץ ושרף, בשדות גידלו בננות, קני סוכר, אננס, בצל, זנגביל, חרדל, דלעת, ומלון. דקלים כדוגמת דקל הסאגו גדלו במטעים. בנוסף גידלו במקום חיות משק כדוגמת ברווזים, תרנגולות, תאו ועזים. גם המסחר פרח והסוחרים שילמו מס תמורת השימוש בנמל מלאקה כנמל ביניים. העיר הוקפה בחומה ובמרכזה הוקמה מצודה, שבמחסניה נשמרו אוצרות הסולטנות ומלאי המזון שלה. מלאקה המשיכה להיות מדינת חסות של הסינים. והסולטאן הקפיד לשלוח לבייג'ינג משלחות בראשות אחד מבניו כמעט מדי שנה. על פי בקשתו, שלח קיסר סין ב-1419 אזהרה למלך סיאם שלא לתקוף את מלאקה.
עם מותו של מגאט איסקנדר שאה עלה על כיסאו בנו, שכונה הסולטאן מוחמד שאה (Muhammad Syah; שלט 1424–1444). כבר עם עלייתו לשלטון נסע הסולטאן החדש לבייג'ינג על מנת לבשר על מות אביו ועלייתו לשלטון. ב-1433 הוא נסע שוב ושהה בסין שנתיים. אלא שב-1434 השתנתה המדיניות בסין. סין נסגרה כלפי חוץ והפסיקה להתעניין במתרחש במדינות אחרות. תרומת הסולטאן הזה למורשת של סולטנות מלאקה הייתה בייצוב השלטון, כאשר קבע את מבנה האדמיניסטרציה העתידית של הסולטנות, שכללה: ראש ממשלה (Bendahara), שר אוצר, ממונה על ביטחון הפנים, מפקד צבא היבשה ומפקד צי, וכן קיבע סדרה ארוכה של מנהגים ואיסורים. בנו, ראג'א איברהים (Raja Ibrahim) עלה לשלטון וכונה הסולטאן אבו שהיד שאה (Abu Syahid; שלט 1445–1446), אף שלא היה בכור בניו. ראג'א קסים (Raja Kassim), אחיו החורג, שהיה בכור בניו של הסולטאן מוחמד שאה, קשר כנגדו יחד עם ראש הממשלה ושר האוצר ובהתקפה מתוכננת נרצח הסולטאן אבו שהיד בדקירות סכין. ראג'א קסים עלה לשלטון הסולטאן מט'פר שאה (Muzaffar Syah; שלט 1446–1456). בתקופתו הדפה הסולטנות שתי התקפות של ממלכת סיאם - ב-1446 התקפה מהיבשה, וב-1456 התקפה ימית.
את הסולטאן מט'פר ירש בנו, ראג'א עבדולה (Raja Abdullah), כסולטאן מנסור שאה (Mansur Syah; שלט 1456–1477). אשתו הייתה האנג לי פו (ה), בתו של שי דאן לי באו מפאלמבאנג. תקופתו נחשבת כתור הזהב של הסולטנות. מדינות רבות בחצי האי המלאי, בסומטרה, בבורנאו ובאיים נוספים, הפכו למדינות חסות של הסולטנות. מלאקה הפכה לגורם חשוב בסחר התבלינים בשל היותה גשר בין איי התבלינים לבין השווקים במזרח התיכון ובאירופה, והסולטנות הייתה למרכז הפצת האסלאם במלאיה ובסומטרה. הסולטאן הבא, עלאא אלדין קרי משובש "אלאודין", ריאיאת שאה (Alauddin Riayat Syah 1488-1477), מת בנסיבות מסתוריות, ועל כיסאו עלה בנו, רג'א מחמוד, כסולטאן מחמוד שאה, סולטאן מלאקה (Mahmud Syah; שלט 1488–1511), הסולטאן השמיני והאחרון של סולטנות מלאקה. בתחילת המאה ה-16 הייתה סולטנות מלאקה בשיא כוחה ותהילתה. העיר הייתה לבירת אימפריה רחבה, מרכז מסחר בבדים מהודו, חרסינה ומשי מסין ותבלינים מאיי התבלינים, כמו גם מרכז להפצת האסלאם בארכיפלג של מלאיה. אך דווקא בתקופה משגשגת זו עתידה הייתה הסולטנות להסתיים בחטף.
ב-11 באוגוסט 1509 הגיעה לנמל מלאקה משלחת בת 5 ספינות פורטוגזיות, שבראשה עמד דיוגו לופש דה סקווירה (Diogo Lopes de Sequeira). קורות משלחת זו עתידות היו להתחיל תקופה חדשה במלאקה – תקופת השלטון הפורטוגזי.
שלטון פורטוגזי (1641-1511).
המשלחת הפורטוגזית הפליגה מגואה שבהודו לאחר שלפורטוגזים נודעה חשיבות מלאקה כמרכז סחר בין הודו לדרום-מזרח אסיה. מטרתה הייתה ליצור קשרי ידידות עם השליט ולהקים במקום את הנציגות הפורטוגזית מזרחית להודו. דה סקווירה שלח לחוף את אחד מהקברניטים עם מכתב ממלך פורטוגל ומתנות עבור הסולטאן. המשלחת התקבלה תחילה בסבר פנים יפות, אלא שסוחרים מוסלמים מהודו וסוחרים ערבים שכנעו את הסולטאן שלא לתת אמון בפורטוגזים כי מטרתם האמיתית היא להשתלט על המסחר של מלאקה. הסולטאן התכוון להשתלט על הספינות, אלא שהמזימה נתגלתה לדה סקווירה שהצליח להימלט עם ספינותיו, אך אחד מקברניטיו וכעשרים מלחים ששהו על החוף נלכדו, וחלקם הוצאו להורג.
התגובה הפורטוגזית הגיעה שנתיים אחר-כך. באפריל 1511 הפליג האדמירל אפונסו דה אלבוקרקי מגואה בראש צי שמנה 17 או 18 אוניות שעל סיפונן כ-1,200 לוחמים. אלבוקרקי דרש מהסולטאן לשחרר את השבויים ולהרשות לו להקים מצודה בחוף. ב-25 ביולי, לאחר שדרישותיו נדחו, הורה אלבוקרקי לתקוף את העיר. התקפה זו נבלמה. בניגוד לעצת מפקדיו החליט אלבוקרקי לתקוף שוב, וב-10 באוגוסט 1511 לכד את העיר. הסולטאן מחמוד שאה ובני משפחתו ברחו צפונה לאולו ברטאם (Ulu Bertam) שבפהנג. אלבוקרקי הורה לבצר את העיר, ועל הגבעה הוקמה מצודה שכונתה "א פאמוסה" ("A Famosa" - "המפורסמת"), תוך שימוש באבנים שנלקחו ממסגד שנהרס וממצבות של קברים. בהמשך נבנו בתוך המצודה ארמון המושל, בית הבישוף, משרדי הממשל, כנסיות, קסרקטינים, מנזר בתי חולים ובית כלא. אלבוקרקי שהה במלאקה עד ינואר 1512 כשהוא דואג לחדש את המסחר ושולח משלחות ידידות לסיאם, ג'אווה, סין ואיי מאלוקו.
הפורטוגזים שלטו בעיר במשך כ-130 שנים. מטרתם המקורית - לשלוט במסחר שבין אירופה והודו לבין דרום-מזרח אסיה באמצעות שליטה במלאקה שבאמצע נתיב השיט - לא הושגה. אומנם במשך השנים גדל שטח העיר בשליטתם והוקמו הרבעים טרנקירה (Tranqueira), ילר (Yler) וסבה (Sabba), אך הקהילה הפורטוגזית הקטנה שישבה בעיר לא הצליחה לשלוט במצר, והסוחרים, שבעבר התרכזו במלאקה, התפזרו בין ערי נמל בסומטרה ובחצי האי המלאי. במשך תקופה זו הותקפה העיר פעמים רבות. הסולטאן מחמוד ניסה לשווא להחזיר את העיר לשליטתו ב-1512 וב-1520. גם בניו, שהקימו סולטנות בג'והור (Johor) שבקצה הדרומי של חצי האי המלאי ובפרק (Perak), תקפו ללא הצלחה את העיר ב-1551 וב-1587. לפורטוגזים היו אויבים נוספים. סולטנות אצ'ה שבקצה הצפוני של סומטרה החלה להתחזק בעקבות כיבוש מלאקה בידי הפורטוגזים, כאשר סוחרים מוסלמים העבירו את מרכז הפעילות לבירה באנדה אצ'ה. סולטנות אצ'ה הייתה בין המדינות הראשונות בדרום-מזרח אסיה לאמץ את האסלאם כדת המדינה, והיא הייתה בת ברית של האימפריה העות'מאנית, אשר העבירה אליה נשק חם ומומחיות בייצורו. בשלב מסוים החלה הסולטנות לנסות לכבוש את מלאקה על רקע היריבות הדתית והכלכלית. ניסיון ראשון נעשה ב-1537. החשש מכוחה העולה של סולטנות אצ'ה הביא את סולטנות ג'והור לכרות ברית עם הפורטוגזים, וב-1568 הצליחו הכוחות של שניהם להדוף התקפה נוספת של אצ'ה. ב-1571 ניסתה שוב סולטנות אצ'ה לכבוש את העיר, אך ללא הצלחה.
ב-1545 הגיע המיסיונר הישועי פרנסיסקו חאווייר למלאקה, והיא שימשה לו בסיס יציאה למקומות שונים בדרום-מזרח אסיה, כדוגמת יפן, איי מאלוקו וסין. ב-1548 הוא הקים את קולג' סאו פאולו במלאקה לבני כל הגזעים. ב-1552 הוא הפליג ממלאקה לסין, אך לא הורשה להיכנס לסין ומת על האי שאנגצ'ואן, 14 קילומטר מהחוף הדרומי של סין. גופתו הובאה למלאקה, והוא נקבר בכנסיית סאו פאולו במלאקה ב-22 במרץ 1553. חודשיים אחר כך הועברה גופתו לגואה, שם היא מצויה עד היום. קבר פתוח בכנסיית סאו פאולו במלאקה מסמן את מקום קבורתו הראשון של חאווייר.