馬來西亞皇家海軍的前身是在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），主要的任務是執行海陸空三棲特別種任務，包括拯救人質、對付海盜劫持、反恐任務、保護商船以及海上鑽油台等。馬來西亞的海軍特種部隊是直接由美國海豹部隊以及英國皇家海軍陸戰隊訓練的，他們相對于馬六甲海峽及其周邊地區的航運安全的最後一道防線。
馬來西亞皇家海軍特種部隊
馬來西亞海軍算是東南亞國家中裝備較好的一支，其艦艇普遍服役年限短，而且起點頗高，均爲歐洲一線産品。馬來西亞海軍擔負著馬六甲海峽以及泰國灣等周邊海域的安全，特別是馬六甲海峽的防護是具有地區戰略價值的。不過目前爲止，馬來西亞海軍的對外依賴性很強，並沒有轉化爲國內造船業技術發展的趨勢，而其是否會邁向多元化發展會是個有意思的問題。