马来西亚皇家海军的前身是在1934年4月27日成立于新加坡的海峡殖民地后备志愿军（Straits Settlement Volunteer Reserve Force）。后备志愿军建立的目的主要是协助英殖民政府对马来半岛及新加坡的防御，特别是在亚洲局势趋于紧张，以及日本推行大东亚共荣圈计划之后。二战期间，英殖民政府在槟城成立分队并改名为马来亚皇家志愿海军（Malay Section of The Royal Navy）。1935年，英国皇家海军部署了“刺槐”级“金琏花”号（Acacia-class, HMS Laburnum）护航炮舰为志愿海军的旗舰。
“金琏花”号
太平洋战争爆发后，马来亚海军一度扩充到1450余人，主要支援同盟国军队在印度及太平洋的行动。不过由于马来亚被日军攻占，人员不断减少，随着日本战败投降，马来亚海军仅剩余600余人，而且由于战后资金缺乏，1947年马来亚海军曾一度被解散。
1948年12月24日，马来亚进入紧急状态期间马来亚海军又恢复运作。1949年3月1日，马来亚海军部队（Malayan Naval Force）条例正式由殖民政府颁布，并以新加坡兀兰（Woodlands）为基地。这一时期，马来亚海军部队的主要任务是进行海岸巡逻，防止游击队从海外获得补给。此外，马来亚海军部队也负责新加坡等港口防务。1952年8月，为表彰马来亚海军部队在紧急状态期间的表现，刚刚登基不久的英女王伊丽莎白二世正式授予皇家马来亚海军（Royal Malayan Navy）的名号。
独立后不久的1958年，马来亚联合邦通过与英国政府谈判，将原属英国海军的资产转移给新成立的马来亚皇家海军。1963年9月16日改名为马来西亚皇家海军，由于已经独立，此处的“皇家”相应指代的是由9个州选举的最高元首暨马来亚三军最高统帅。1960年代的印马对抗期间，马来西亚皇家海军负责东马地区的巡逻防务。与印尼的对抗结束后，在东姑·阿卜杜勒·拉赫曼首相任期内，马来西亚皇家海军高层逐步马来西亚化，时任皇家海军总司令的海军上将K.塔纳巴拉辛格姆也得到了东姑等领导的信任。在他们的共同推动努力下，马来西亚皇家海军逐步从一支海岸防御海军发展成近海海军。1970年以后，马来西亚皇家海军购入了若干新舰，如从英国购买了“美人鱼”号（HMS Mermaid ）护卫舰并更名为“汉都亚”号（KD Hang Tuah），汉都亚是马六甲王国时期著名的海军将领，而KD则是Kapal Diraja，马来语中“皇家的舰艇”之意。1990年代后，马来西亚皇家海军加速了舰艇的现代化和多样化，购入了多艘辅助舰、扫雷舰、水文船等。
“汉都亚”号
马来西亚皇家海军现有1.4万人左右，由海军司令部负责指挥和日常管理，下设海军总参谋部、舰队、海军情报部、海军总调查部和舰队训练与教育部，海军副司令兼任总参谋长。舰队划分为海军系统部、第一海军军区、第二海军军区和第三海军军区。第一海军军区防区为马来西亚半岛以北的海域，第二海军军区负责东马来西亚（加里曼丹部分防务工作），第三海军军区则负责马来半岛以南海域的防务，包括马六甲海峡。
布斯特德重工
海军总部位于霹雳州曼绒县的卢穆特（Lumut），卢穆特还有布斯特德重工船坞（Boustead Heavy Industries Corporation Berhad），是马来西亚最大的造船基地和船坞所在地。第一海军军区司令部在彭亨州关丹的丹戎格朗（Tanjung Gelang），第二海军军区司令部位于柔佛州的丹戎边加兰（Tanjung Pengelih），第三海军军区司令部在吉打州浮罗交怡丹戎盖拉克（Tanjung Gerak）。除此之外，柔佛州丹戎边加兰（Tanjung Pengelih）设有皇家海军征召培训基地，雪兰莪州英达岛（ Pulau Indah）设有国家水文中心，柔佛州中岩礁（ Middle Rocks）有阿布巴卡尔海事基地。在东马来西亚则有纳闽（Labuan）基地，沙巴州山打根（Sandakan）、仙本那（Semporna）、庇实邦加（Sepanggar），砂劳越的古晋（Kuching）和民都鲁（Bintulu）也都设有基地，其中，庇实邦加为唯一的潜艇基地。马来西亚还在一些离岸岛礁设立了海军站，包括Lima、Uniform、Mike、Sierra、Papa五个海军站，对应无线电的L、U、M、S、P呼号。
马来西亚海军基地分布
在舰队下马来西亚海军设置了分舰队（Squadron），下设包括第21、23护卫舰分舰队；第22、24轻型护卫舰分舰队；第26反水雷分舰队；第31多用途支援舰分舰队；第32海运分舰队；第36水文分舰队；第27训练分舰队；第1导弹艇分舰队；第6快速巡逻艇分舰队；第13巡逻艇分舰队；快速运兵船分舰队；潜艇支援舰分舰队；拖轮分舰队。
马来西亚海军的装备水准不低，包括2艘法国建造的“鲉鱼”级（Scorpéne）常规潜艇，是马来西亚海军历史上第一次拥有潜艇，2009年入役。“鲉鱼”级水下排水量1711吨，可以发射意大利制造的“黑鲨”533毫米重型鱼雷和SM39潜射反舰导弹。2艘“鲉鱼”级分别为“东姑·阿卜杜勒·拉赫曼”号（KD Tunku Abdul Rahman）和“敦阿卜杜勒·拉扎克”号。 （KD Tun Abdul Razak）
东姑·拉赫曼号
护卫舰上，马来西亚海军有2艘“叻古”级（Lekiu）护卫舰，为英国BAE公司建造的F2000型护卫舰，1999年交付，都部署在第23护卫舰分舰队，满载排水量2300吨，搭载“海狼”防空导弹和MM40“飞鱼”反舰导弹。2艘“叻古”级分别为F29“惹拔”（KD Jebat）、F30“叻古”（KD Lekiu） 。此外，马来西亚即将开始接收6艘法国制“追风”级护卫舰，马来西亚称为“马哈拉·惹里拉”级（Maharaja Lela Class），其排水量约3100吨，搭载法国的“米卡”垂直发射型防空导弹和挪威的海军打击导弹。
惹拔号护卫舰
“马哈拉·惹里拉”级
轻型护卫舰则有2艘德国制的“卡斯图里”级（Kasturi ）和4艘意大利制造的“海军上将”级构成。“卡斯图里”级1984年交付，部署在第22轻型护卫舰分舰队，满载排水量1850吨，主要武器为8枚MM38型反舰导弹，2艘分别为F25“卡斯图里”（KD Kasturi ）和F26“力桥” （KD Lekir） 。4艘“海军上将”级本来为伊拉克购买的“阿萨德”级，但是由于海湾战争制裁而被悬置直至马来西亚海军看中，4艘分2批分别在1997和1999年交付，隶属于第25轻型护卫舰分舰队。其满载排水量625吨，主要装备“阿斯派德”防空导弹和“奥托马”反舰导弹，4艘分别为F134“海军上将韩那丁” （KD Laksamana Hang Nadim）、F135“海军上将敦阿卜杜勒·贾米尔”（KD Laksamana Tun Abdul Jamil）、F136“海军上将穆罕默德·阿明”（KD Laksamana Muhammad Amin） 、F137“海军上将丹普斯曼”（KD Laksamana Tan Pusmah）。
力桥号
海军上将穆罕默德·阿明号
“吉打”级（Kedah-class）巡逻舰，为马来西亚海军按照德国MEKO100型护卫舰打造的巡逻舰，虽然设计定位为轻型护卫舰并且满载排水量高达1850吨，但由于马来西亚海军取消了导弹武器，仅仅将“吉打”级作为巡逻舰使用。原本马来西亚方面打算订购27艘，但是由于交付延误和预算超支，最后仅有6艘于2006-2010年陆续服役，包括F171“吉打”（ KD Kedah）、F172“彭亨”（KD Pahang）、F173“霹雳”（KD Perak）、F174“登嘉楼”（KD Terengganu）、F175“吉兰丹”（KD Kelantan）、F176“雪兰莪”（KD Selangor）。马来西亚还在2018年向中国订购了4艘濒海任务舰，定位与此相似。
彭亨号
马来西亚海军手中还有4艘“首领”级（Perdana）导弹艇，其为为德国海军建造的148型导弹艇的另外出口版本，满载排水量265吨，1972-1973年服役。4艘瑞典建造的“超级”级（Handalan）导弹艇，满载排水量268吨，1976年服役。这两款导弹艇都携带8枚MM38型反舰导弹。除了导弹艇，6艘“大白鲨”级（Jerung）、2艘“马来剑”级（Keris）炮艇和14艘CB90/CB90HEX快速突击艇则是近岸巡逻的一部分。
首领级
4艘意大利产的“玛哈米如”级（Mahamiru）扫雷舰是马来西亚海军反水雷战的核心成员。2艘德国制4300吨的“斯里因德拉·沙克帝”级（Sri Indera Sakti）多用途支援舰是马来西亚补给舰队的核心。1艘“美佳巴迪”（Mega Bakti）则是新加坡产的，也是唯一一艘潜艇支援舰。此外，马来西亚还有5艘运兵船、3艘训练舰（包括退役的汉都亚号）和2艘水文调查船。
斯里因德拉·沙克帝号
在海军航空兵上，马来西亚海军有6架“超级大山猫”直升机、6架AS555N型直升机作为舰载直升机使用。此外，马来西亚海军刚刚购入了6套美制“扫描鹰”无人机。
马来西亚的超级大山猫直升机
马来西亚海军还有一支特种部队，即马来西亚皇家海军特种部队（Pasukan Khas Laut，PASKAL），主要的任务是执行海陆空三栖特别种任务，包括拯救人质、对付海盗劫持、反恐任务、保护商船以及海上钻油台等。马来西亚的海军特种部队是直接由美国海豹部队以及英国皇家海军陆战队训练的，他们相对于马六甲海峡及其周边地区的航运安全的最后一道防线。
马来西亚皇家海军特种部队
马来西亚海军算是东南亚国家中装备较好的一支，其舰艇普遍服役年限短，而且起点颇高，均为欧洲一线产品。马来西亚海军担负着马六甲海峡以及泰国湾等周边海域的安全，特别是马六甲海峡的防护是具有地区战略价值的。不过目前为止，马来西亚海军的对外依赖性很强，并没有转化为国内造船业技术发展的趋势，而其是否会迈向多元化发展会是个有意思的问题。