马六甲名称来源极富戏剧性。１４００年前流亡的苏门答腊王子拜里米苏剌，在马六甲河畔狩猎，正靠在一棵大树旁休息时，见到他的猎狗追逐一只鼠鹿，鹿返身攻击猎狗，把狗反击驱逐到河中，鼠鹿的勇敢斗志使他大喜，他认为这是一块福地，鼠鹿有这般勇气，此地足以居留，就决定在这里建立新的王国。他从部下口中得知，他所靠的大树是棵满剌加树，因此就将这地方命名为“满剌加＂，后来他成为马六甲的开国之君。
　　马六甲王朝初期，整个马来半岛都在暹罗（即今泰国）的势力范围下，马六甲王朝饱受暹罗欺压。爪哇的满者伯夷当时也存有非分之想，永乐元年（公元１４０３年），明成祖派遣内官尹庆到访南洋宣抚，拜里米苏剌想藉中国声威来减轻暹罗欺凌，便派使者随从乘尹庆回朝的船只到南京晋见明朝皇帝。明成祖正式承认马六甲王朝的第一个统治者，还赐赠诰印、冠带和袍服、黄伞等厚礼，并且封赐他为“满剌加国王＂。
　　郑和有效地制止了暹罗对马六甲的入侵，严厉打击海盗，调解邻国间的矛盾与冲突，维护了该地区的安定，从此马六甲也脱离了暹罗，迅速繁荣起来。马六甲使者王慕义愿同中国列郡，岁效职遣，请封其山为一国之镇。明成祖从之，亲自撰写“马六甲镇国山碑＂，置于马六甲西面山上，可惜这块珍贵碑文迄今未出土。《明史》中碑文内容有完整的记载，其原文如下：
　　西南巨海中国通输天灌地亿载同
　　洗日浴月光景融两岸露石花木侬
　　金花宝钿生青红有国于此民俗雍
　　王好善意思朝宗愿比内部依华风
　　
　　出入导从强盖重仪文褐袭礼虔恭
　　大书贞石表尔忠尔国西山永镇封
　　山居海伯翕扈从皇考从降在被穹
　　后天监视亡弘隆尔众子孙万福崇
　　郑和的到访对于马来西亚的历史发展起过绝对的影响作用，马六甲成为东西方货物转口中心，中国人带来了金银、瓷器和丝绸，印度人带来了纺织品和铜器，阿拉伯人带来了香料、珍珠、胡椒等。
　　郑和下西洋首次造访后，马六甲国王多次率领庞大使团随郑和船队到中国，和明朝展开频繁的朝贡贸易，加强了双方的友好关系，成为马来西亚历史发展的起源和马中友好关系的起源。公元１４１１年，拜里米苏剌偕王妃与随从数百人随郑和晋京朝贡，带着珍珠、玛瑙、珊瑚、黑猿和白鹿等纳贡物品，表达对中国的万分感激之情。此时正值马六甲王朝建国之初，也是马来西亚历史发展的起源，为５５４年后（１９５７年）的马来西亚独立打下了强有力的历史基础。
　　在中国支持下马六甲王朝总共有８位苏丹共计统治１０８年，公元１４５９年，第五位马六甲国王查化驾崩，其初子拉惹阿都拉继位为第六世苏丹，称为苏丹满速沙。在苏丹满速沙统治下，马六甲渐渐发展成为东南亚最大的商业中心，这是马六甲王国史上黄金时代的开端。
　　满速沙继位不久，派人赴中国南京朝贡，请中国皇帝把女儿嫁给他，明天子为促进彼此的友谊，派使臣率领百艘大船及赐给汉丽宝公主的５００人护送汉丽宝公主下嫁苏丹满速沙。
　　当初汉丽宝公主带来的５００名宫女多与土著结婚，渐渐学会了马来话并融入当地社会，成为最早的华侨和移民。汉丽宝公主远嫁到马六甲后，生一王子叫明马，她把干戈化为玉帛，解决了许多外交危机。马来人在戏剧里或剧本里至今仍在宣扬汉丽宝公主，马六甲至今还有汉丽宝街。
　　汉丽宝公主的传说是根据《马来纪年》第十五章的记载，可是中国公主下嫁苏丹满速沙之说，却不见记载在明史。这足可以说明６００年前郑和早已奠定了中马两国的深厚友谊。