จารึกตรังกานู (Terengganu Inscription) เป็นจารึกที่เก่าแก่ที่สุดที่ใช้อักษรยาวีเขียนภาษามลายูใน ค.ศ. 1303 เป็นหลักฐานถึงอิทธิพลของศาสนาอิสลามในระยะแรก

เจ้าชายปรเมศวร (Paramesawara) เป็นรายาพระองค์แรกของอาณาจักรมะละกา อย่างไรก็ตามประวัติความเป็นมาและเรื่องราวของเจ้าชายปรเมศวรยังคงเป็นที่ถกเถียงเนื่องจากเอกสารประวัติศาสตร์ระบุเหตุการณ์ไม่ตรงกัน พงศาวดารสยาราะฮ์มลายู (Sejarah Melayu) ซึ่งถูกบันทึกในคริสต์ศตวรรษที่ 17 ระบุว่าเจ้าชายปรเมศวรเป็นรายาองค์สุดท้ายแห่งอาณาจักรสิงคปุระ พระเจ้าวิกรมวรรธนะ (Wikromwardhana) แห่งมัชปาหิตยกทัพเรือเข้าโจมตีเมืองสิงคปุระ รายาปรเมศวรสูญเสียเมืองสิงคปุระให้แก่ทัพเรือชวาและอาณาจักรสิงคปุระสิ้นสุดลง ในหนังสือเรื่องซุมาโอเรียนตัล (Suma Oriental) ของโตเมปิเรส (Tome Pires) นักเดินทางชาวโปรตุเกส ระบุว่าเจ้าชายปรเมศวรเป็นเจ้าชายจากเมืองปาเล็มบังของศรีวิชัย ซึ่งเจ้าชายปรเมศวรยกทัพเรือจากเมืองปาเล็มบังเข้ายึดเมืองสิงคปุระไว้ให้แก่ตนเอง แต่เนื่องจากเมืองสิงคปุระในขณะนั้นเป็นประเทศราชของสยาม ทัพเรือจากสยามจึงยกมาเข้ายึดเมืองสิงคปุระกลับคืนไป อาณาจักรสิงคปุระสิ้นสุดลงใน ค.ศ. 1398 จากการรุกรานของสยามหรือชวา ทำให้เจ้าชายปรเมศวรต้องเสด็จหลบหนีไปทางตะวันตกบนคาบสมุทรมลายู ไปยังแคว้นมูอาร์ (Muar) เจ้าชายปรเมศวรประทับใต้ต้นมะขามป้อม เมื่อสุนัขล่าเนื้อของเจ้าชายปรเมศวรไล่ติดตามละมั่งตัวหนึ่งปรากฏว่าละมั่งนั้นหายตัวไปเป็นสัญญาณมงคล เจ้าปรเมศวรจึงสร้างเมืองมะละกาขึ้นบริเวณต้นมะขามป้อมนั้นเป็นจุดกำเนิดของอาณาจักรมะละกา

เศรษฐกิจของอาณาจักรมะละกาเกิดจากการควบคุมเส้นทางการค้าผ่านทางช่องแคบมะละกา รัฐมะละกาในสมัยแรกต้องเผชิญกับมหาอำนาจทั้งสองได้แก่สยามอาณาจักรอยุธยาจากทิศเหนือและชวามัชปาหิตจากทิศใต้ ใน ค.ศ. 1405 พระจักรพรรดิหย่งเล่อแห่งราชวงศ์หมิงส่งกองทัพเรือทูตนำโดยเจิ้งเหอ (จีน: 鄭和; พินอิน: Zhèng Hé) มายังทะเลใต้ เจ้าชายปรเมศวรจึงหันไปผูกสัมพันธไมตรีกับจีนราชวงศ์หมิงเพื่อแสวงหาความคุ้มครองทางการเมืองคานอำนาจกับสยามและชวา ใน ค.ศ. 1411 เจ้าชายปรเมศวรพร้อมทั้งเชื้อวงศ์และขุนนางข้าราชการโดยสารติดไปกับกองเรือสำรวจของเจิ้งเหอเดินทางไปเข้าเฝ้าพระจักรพรรดิหย่งเล่อ

อาณาเขตสูงสุดของรัฐสุลต่านมะละกา ประกอบไปด้วยส่วนใหญ่ของแหลมมลายูรวมทั้งดินแดนฝั่งเกาะสุมาตราและหมู่เกาะรีเอา (Riau Islands) ในขณะที่รัฐมลายูทางเหนือได้แก่ปัตตานี ไทรบุรี และกลันตัน อยู่ภายใต้อิทธิพลของอยุธยา

ในสมัยของรัฐมะละกาศาสนาอิสลามนิกายซุนหนี่ได้เผยแพร่มาถึงยังคาบสมุทรมลายู ผ่านทางเส้นทางการค้าขายกับชาวเปอร์เซียและอินเดีย โดยศาสนาอิสลามในมะละกาได้รับอิทธิพลจากรัฐสมุเดราปาไซ (Samudera-Pasai) ทางเหนือของเกาะสุมาตรา เอกสารทางประวัติศาสตร์ของรัฐอื่น ๆ ต่างระบุอ้างว่ารัฐของตนรับศาสนาอิสลามมาก่อนหน้ารัฐมะละกาแล้ว เช่น พงศาวดารฮิกายะต์เมอรงมหาวังสา (Hikayat Merong Mahawangsa) ของไทรบุรี ระบุว่ารัฐไทรบุรีนับถือศาสนาอิสลามมาตั้งแต่ ค.ศ. 1136 มีการค้นพบจารึกตรังกานู (Terengganu Inscription) ที่รัฐตรังกานู จารึกขึ้นใน ค.ศ. 1303 เป็นจารึกภาษามลายูคลาสสิก (Classical Malay) โดยมีการใช้อักษรยาวี (Jawi script) เป็นครั้งแรกซึ่งประยุกต์มาจากอักษรอาหรับมาเพื่อใช้เขียนภาษามลายู อาณาจักรมะละกาได้พัฒนาขึ้นเป็นศูนย์กลางทางการเมืองและวัฒนธรรมของโลกมลายู เมื่อมะละการับและส่งเสริมศาสนาอิสลามทำให้ศาสนาอิสลามสามารถประดิษฐานในโลกและวัฒนธรรมมลายู หนังสือซุมาโอเรียนตัลของโตเมปิเรสระบุว่าโอรสของรายาปรเมศวรรับศาสนาอิสลามเป็นศาสนาประจำมะละกะและใช้ตำแหน่ง “สุลต่าน” เป็นผู้ปกครองรัฐมะละกา ทำให้มะละกากลายเป็นรัฐสุลต่าน (Sultanate) ในขณะที่สยาราะห์มลายูระบุว่ามะละการับศาสนาอิสลามในสมัยของรายาองค์ที่สาม ผู้ซึ่งเปลี่ยนมาใช้ชื่อว่าสุลต่านมูฮาหมัดชาฮ์ (Muhammad Shah) ระบบราชการของรัฐมะละกาประกอบไปด้วยตำแหน่งต่าง ๆ ตำแหน่งสูงสุดคือเสนาบดีเรียกว่าเบินดาฮารา (Bendahara) ต่อมามีหัวหน้าองครักษ์เรียกว่าตำมะหงง (Temenggong) แม่ทัพเรือเรียกว่าลักษมณา (Laksamana) และเจ้ากรมท่าเรือเรียกว่าชาฮ์บันดาร์ (Syahbandar)

บุหงามาศดันเปรัก (Bunga mas dan perak) หรือต้นไม้เงินต้นไม้ทอง เป็นเครื่องบรรณาการซึ่งรัฐมลายูทางภาคเหนือได้แก่ไทรบุรี และกลันตัน ต้องส่งให้แก่สยามอาณาจักรอยุธยา

ในสมัยของสุลต่านมันซูร์ชาฮ์ (Mansur Shah) เป็นยุครุ่งเรืองของรัฐสุลต่านมะละกา สุลต่านมันซูร์ชาฮ์ประสบความสำเร็จในการขยายดินแดนข้ามฝั่งไปยังเกาะสุมาตรามีอำนาจเหนือแคว้นรีเอา (Riau) รวมทั้งเข้าครอบครองหมู่เกาะรีเอา (Riau islands) ในขณะที่รัฐมะละกากำลังเรืองอำนาจอยู่ทางใต้ของแหลมมลายูนั้น รัฐมลายูต่าง ๆ ในภาคเหนือได้แก่ ไทรบุรี และกลันตันซึ่งเดิมอยู่ภายใต้อำนาจของอาณาจักรนครศรีธรรมราช เมื่อนครศรีธรรมราชถูกรวมเข้ากับอาณาจักรอยุธยารัฐมลายูเหล่านั้นจึงขึ้นกับสยามอาณาจักรอยุธยาด้วย มีการส่งบรรณาการเป็นต้นไม้เงินต้นไม้ทองหรือเรียกว่าบุหงามาศ (Bunga mas) ให้แก่อยุธยาเป็นระยะ รัชสมัยของสมเด็จพระบรมไตรโลกนาถสยามอยุธยาส่งกองทัพเข้าโจมตีรัฐมะละกาทางบกซึ่งเอกสารฝ่ายไทยและฝ่ายมลายูให้รายละเอียดเหตุการณ์ต่างกัน พงศาวดารฉบับพันจันทนุมาศ (เจิม) ระบุว่า "ศักราช ๘๐๓ ปีระกาตรีศก ( ค.ศ. 1441) แต่งทัพไปเอาเมืองมะละกา"[3] พงศาวดารกรุงเก่าฉบับหลวงประเสริฐระบุว่า "ศักราช ๘๑๗ กุนศก ( ค.ศ. 1455) แต่งทัพให้ไปเอาเมืองมลากา"[4] ส่วนสยาระฮ์มลายูกล่าวว่ากษัตริย์สยามพระนามว่าบูบันยาร์ (Bubanyar) ทรงแต่งทัพเข้ารุกรานมะละกาสองครั้ง[5] ครั้งแรกนำโดยอาวีชาครี (Awi Chacri ออกญาจักรี?) ยกทางบกมายังเมืองปะหัง ครั้งที่สองนำโดยอาวีดีชู (Avidichu ออกญาเดโช?) ซึ่งทั้งสองครั้งแม่ทัพตุนเปรัก (Tun Perak) สามารถนำทัพมลายูขับทัพฝ่ายสยามออกไปได้

ใน ค.ศ. 1509 ทหารชาวโปรตุเกสชื่อ ดีโยกู ลอปึช ดึ ซึไกรา (Diogo Lopes de Sequeira) เดินทางมายังเมืองมะละกาเพื่อขอเจรจาเปิดเส้นทางการค้า แต่บรรดาพ่อค้าชาวอินเดียมุสลิมในมะละกามองว่าโปรตุเกสเป็นศัตรูทางการค้าและทางศาสนา จึงแนะนำให้สุลต่านมาฮ์มุดชาฮ์ (Mahmud Shah) ต่อต้านอิทธิพลของโปรตุเกส สุลต่านมาฮ์มุดชาฮ์มีคำสั่งให้ลอบสังหารดึ ซึไกรา ดึ ซึไกราไหวตัวทันหลบหนีไปแต่ทางการมะละกาสามารถจับกุมชาวโปรตุเกสมาขังไว้บางส่วน ใน ค.ศ. 1511 อาฟงซู ดึ อัลบูแกร์กึ ข้าหลวงโปรตุเกสประจำเมืองกัว ยกทัพโปรตุเกสมายังเมืองมะละกาเพื่อเรียกร้องให้สุลต่านมะละกาปล่อยตัวชาวโปรตุเกส เมื่อสุลต่านไม่ยอมปล่อยตัวชาวโปรตุเกส ดึ อัลบูแกร์กึจึงยกทัพเข้าบุกยึดเมืองมะละกาได้อย่างรวดเร็ว สุลต่านมาฮ์มุดชาฮ์และครอบครัวหลบหนีออกจากเมืองมะละกา ทำให้รัฐสุลต่านมะละกาซึ่งดำรงอยู่มาเป็นเวลาประมาณหนึ่งร้อยปีสิ้นสุดลง สุลต่านมาฮ์มุดชาฮ์หลบหนีไปยังเมืองกัมปาร์ (Kampar) บนเกาะสุมาตราและอยู่ที่นั่นจนกระทั่งเสียชีวิต