Formeel gesproken werd de Koninklijke Marine met deze naam pas in 1905 aangesproken. De tradities van de Nederlandse Koninklijke Marine kunnen echter worden teruggevoerd op de instelling van de Ordonnantie op de Admiraliteit in 1488, waarmee de Admiraliteit van Veere door Koning Maximiliaan I werd opgericht. Via Admiraliteiten van de Republiek, de Staatse Vloot en de Koninklijke Nederlandse Zeemacht, ontstond de Koninklijke Marine zoals we die heden ten dage nog kennen.

De geschiedenis van de Nederlandse zeemacht is terug te voeren op de opkomst van de zeevaart in Vlaanderen en het toenmalige belang van de Scheldedelta, Walacra geheten. Deze naam kan nog steeds worden herkend aan het (schier)eiland Walcheren. In 1012 werd deze delta te leen gegeven aan de Graaf van Vlaanderen, Boudewijn IV en vanaf 1018 behoorde het ook bestuurlijk aan het graafschap Vlaanderen.

In 1242 werd door Johanna van Constantinopel, gravin van Henegouwen en Vlaanderen, een keur verleend aan de zogenaamde Vier Ambachten, te weten Boekhouter Ambacht, Assender Ambacht, Axeler Ambacht en Hulster Ambacht waardoor zij in samenwerking bepaalde privileges en volmachten tot zelfbestuur ontvingen.

Het bestuur over het gebied ten noorden van de Honte, viel vanaf 1323 onder de graaf van Henegouwen-Holland die hiermee Graaf van Zeeland werd, dat samen met Holland en Henegouwen tussen 1323 en 1433 een unie vormde onder het Henegouwse en Beierse huis en tussen 1433 en 1581 met Vlaanderen, Artesië, Henegouwen, Namen, Holland en Zutphen een uni onder het Bourgondische en Habsburgse huis vormde. Vanaf 1482 bestond dit graafschap Zeeland uit Zeeland Bewestenschelde (het gebied tussen de Ooster- en Westerschelde) en Zeeland Beoostenschelde (het gebied ten noorden van de Oosterschelde) en hoorde tot de Habsburgse Nederlanden. De Vier Ambachten zelf bleven deel uitmaken van Vlaanderen tot gedurende de Tachtigjarige Oorlog het noordelijke gedeelte door de Republiek der Verenigde Nederlanden werd ingelijfd. Pas in 1664 werd definitief de grens tussen de Noordelijke en de Zuidelijke Nederlanden vastgesteld, waarbij het gebied van de Vier Ambachten werden verdeeld in een Nederlands en Belgisch deel (Zeeuws-Vlaanderen en Vlaanderen).

Vlaanderen had in die begintijd regelmatig last van Hollandse kapers en de Vier Ambachten moesten dan ook bewapende schepen leveren om koopvaardij- en vissersschepen te beschermen tegen deze kapers. Tot een echter krijgsmacht op zee kwam het echter nog niet. Om bepaalde expedities of tochten van schepen afdoende te beschermen werd de zogenaamde konvooivaart uitgevonden. Hierbij liet men schepen in groepen varen en liet deze bewapenen of beschermen door bewapende schepen. Om tot een zeker coördinatie te komen werd één van de schippers aangewezen als commandant van een dergelijk konvooi. Deze schipper werd aangeduid als Admiraal, een verbastering van het Arabische emir-al-bahr (commandant van de zee).

Dit was in die tijd nog een tijdelijke functie. In 1356 wilde de Vlaamse graaf Lodewijk van Male tijdens de Successieoorlog tussen het Hertogdom Brabant en het Graafschap Vlaanderen, de havenstad Antwerpen veroveren. Voor een vloot van twaalf schepen die hiermee werd belast, werd Jacob Buuc aangesteld als Admiraal van der vlote. Na de beschieting door deze vloot, gaf de stad zich over. De Vlaamse Westvloot, die onder andere in de Golf van Biskaje opereerde, stelde eveneens voor konvooivaarten Admiraals aan. Om deze vloot te beschermen tegen Engelse kapers, benoemde Lodewijk van Male in 1377 voor het eerst een permanentere admiraal. Mathys Claissone werd toen Admirael der Vlaemsche Vlote. Het zou nog tot 1382 duren voordat de functie van Admiraal permanent werd. Jan Buuc werd toen aangesteld als Admiraal. Nadat hij gevangen werd genomen door de Engelsen nam Jan van Cadzant het ambt over tot hij in 1396 overleed.

In het noorden had Albrecht van Beieren in Holland ten behoeve van zijn expedities tegen de Friezen in 1397 en 1398 voor het eerst Admiraals aangewezen. Dit waren respectievelijk de Heer van Egmond en de Heer van Heenvliet. De term Admiraal werd echter alleen voor deze expedities gebruikt. Ten tijde van Filips de Stoute en Filips de Goede, werden de meeste Nederlandse gewesten onder direct heerschappij van Bourgondië gebracht. Door het instellen van een Admiraal-generaal voor Artesië, Boulogne, Holland, Zeeland en Friesland werd voor het eerst formeler een Admiraal buiten Vlaanderen ingesteld. In 1454 werd een Grote Raad ingesteld die een soort Admiraliteitsraad vormde. Ondanks deze twee meer permanentere Admiraals, werd het Admiraalschap veelal nog steeds tijdelijk ingevoerd voor vloten tijdens expedities of oorlogen. Om de Bourgondische en Vlaamse invloed te beteugelen, vormde Hendrik II van Borselen, de Heer van Veere een eigen zeemacht. Door zijn machtige positie op Walcheren en het bezit van een eigen vloot, kon hij veel invloed uitoefenen binnen het Bourgondische rijk.

Toen Maria van Bourgondië overleed en Vlaanderen het regentschap van Maximiliaan van Oostenrijk weigerde te erkennen brak een Vlaamse opstand uit. De noordelijke admiraal en vele Nederlandse edelen schaarden zich achter Vlaanderen. De toenmalige Admiraal van Vlaanderen, Joost van Lalaing overleed rond deze periode en de noordelijke Admiraal, Filips van Kleef, werd in 1485, onder ontslag van alle andere op dat moment in de Nederlanden bestaande Admiraals, benoemd tot de eerste Admiraal der Nederlanden. De bevoegdheden van deze Admiraal werden bij de Ordonnantie op de Admiraliteit van 8 januari 1488 uitgevaardigd. De oorlogsvloot van de Admiraal werd, onder invloed van de Heer van Veere, in 1540 verplaatst van Sluis naar Veere, waarmee het ambt van Admiraal in handen van het Huis van Veere kwam. Dit huis zou de Admiraal leveren van 1491 tot 1558. Om Vlaanderen tevreden te houden werd in Duinkerken een vice-Admiraliteit gevestigd. De Ordonnantie op de Admiraliteit lokte echter de nodige protesten uit in de Noordelijke Nederlanden. In Holland met name vond men dat de Stadhouder tevens de functie van Admiraal diende uit te voeren. Het zou echter nog tot 1558 duren voordat de functie van de Admiraliteit van Veere zou worden betwist.

In 1558 overleed Maximiliaan van Bourgondië en werd het Admiraalschap in de Nederlanden verdeeld over twee functies. Prins Willem van Oranje werd Stadhouder van Holland, Zeeland en Utrecht en tevens Generaal-admiraal. De Graaf van Horn, Filips van Montmorency werd Admiraal van de Admiraliteit van Veere. Toen hij in 1560 de zetel van de admiraliteit naar Gent verplaatste en in 1561 de vloot verkocht was de invloed van de admiraal voorbij. Tussen Holland en de Zuidelijke Nederlanden werd uiteindelijk in een compromis besloten dat de Admiraliteit van Gent werd erkend door de Noordelijke Nederlanden indien op voordracht van Holland in Holland een Luitenant-admiraal kon worden aangesteld. Hoewel hiervoor op 29 april 1567 Nicolaas van Assendelft werd aangesteld, bleven er meningsverschillen over de aansturing van de vloten bestaan. Uiteindelijk werd na de door van de Graaf van Horn, Maximiliaan van Hénin-Liétard, graaf van Bossu als Admiraal aangesteld. Hij zou de laatste Admiraal der Nederlanden worden.

In 1568 begon De Opstand van de Nederlanden tegen het Habsburgse gezag. Lodewijk van Nassau, de broer van Willem van Oranje en diens secretaris, had een aantal Zeeuwse schippers voorzien van kaperbrieven om koopvaardijschepen te mogen beroven. Bij deze kapers zaten diverse edelen die onder de Habsburgers hun privileges hadden verloren en werden de Geuzen of Watergeuzen genoemd. Eén van hen, Lodewijk van Boisot, kreeg de titel Admiraal van Zeeland. In 1575 volgden de instellingen van een Admiraliteit in Zuid-Holland en in Noord-Holland. Rond 1585 ontstond ook de Admiraliteit van Amsterdam. Deze stad was tot 1578 nog Spaansgezind gebleven.

Tijdens De Opstand werd de Graaf van Leicester, Robert Dudley benoemd tot landvoogd en hij stelde in 1586 een nieuwe instructie op voor de Admiraliteit. Er werden drie Admiraliteitsraden opgericht in Veere, Rotterdam en Hoorn en te Oostende werd de Admiraliteit van Oostende opgericht, die echter onder druk van Zeeland een jaar later weer werd opgeheven. De ontwikkelingen tijdens De Opstand maakten een beter bestuur van maritieme operaties noodzakelijk. In 1596 werd hiervoor een Generaal College van Admiraliteit opgericht. Van echte samenwerking tussen de Admiraliteiten kwam echter weinig terecht. Op 13 augustus 1597 werd een Instructie voor de Admiraliteiten vastgelegd door de Staten-Generaal. Er werden vijf Colleges ter Admiraliteit vastgelegd. Dit waren de Admiraliteit van Zeeland (Middelburg), de Friese Admiraliteit (Dokkum, na 1645 Harlingen), de Admiraliteit van het Noorderkwartier (Hoorn en Enkhuizen), de Admiraliteit van Amsterdam en de Admiraliteit van de Maze (Rotterdam). Deze colleges werden bestuurd door de Heeren Raden ter Admiraliteit en de Prins van oranje was Admiraal-generaal en voorzitter van alle colleges. Binnen de colleges liet hij zich vertegenwoordigen door een Luitenant-admiraal. Bij afwezigheid van de Admiraal-generaal had de Staten-Generaal de eindverantwoordelijkheid bij monde van de Raadspensionaris, de secretaris van de Staten van Holland. Hoewel de diverse gewesten veel eigen invloed op de Admiraliteiten hadden, maakte landelijk de Admiraliteit van Amsterdam over het algemeen de dienst uit. De belangrijkste taak van de Admiraliteiten was de bouw, het onderhoud en de uitrusting van de oorlogsvloot. Deze oorlogsvloot diende ter bescherming van de handelsvloten van met name de VOC. De Staatse Vloot bezat echter zelf weinig schepen. De meeste handelsschepen werden zelf bewapend en werden ingezet samen met schepen die bezit waren van de vijf admiraliteiten.

Gedurende de 17e eeuw lukte het de Republiek om met haar Staatse Vloot de heerschappij van de Spanjaarden op zee te breken en samen met Zweden een heerschappij in de noordelijke wateren te vestigen. Langzaam maar zeker zorgde dit er voor dat Engeland zich bedreigd voelde. Dit leidde uiteindelijk tot de Engels-Nederlandse Oorlogen. Nadat ook hier de Nederlanden heer en meeste op de zeeën werden, werd in 1675 bij de Vrede van Westminster deze heerschappij bevestigd. Nadat Willem III koning van Engeland werd, kon de Nederlands-Engelse combinatie heersen op de wereldzeeën.

Bij aanvang van de 17e eeuw was het gangbaar tijdens oorlogen de relatie kleine Staatse Vloot te versterken met bewapende koopvaardijschepen. Wijzigingen in tactieken en technieken maakten het echter steeds belangrijker om tot uniformiteit te komen. Hierdoor werd in 1653 door de Staten-Generaal besloten over te gaan tot de aanschaf van zestig oorlogsschepen ten behoeve van de Staatse Vloot. Het bevel over deze vloot kwam in deze tijd te liggen bij Michiel de Ruyter. In de jaren 1660 werden nog eens zestig schepen besteld, waardoor eind 17e eeuw de Nederlanden een oorlogsvloot van ruim honderd linieschepen, fregatten en overige lichtere schepen kon inzetten. De grootsten hiervan beschikten over 80 tot 96 stukken geschut met als vlaggenschip de Zeven Provinciën. Manschappen werden meestal voor slechts één campagne aangesteld. Officieren werden echter veelal in vaste dienst genomen. Vanaf 1665 werd op elk schip een regiment scheepssoldaten ingesteld. Dit zou later zich ontwikkelen tot het Korps Mariniers.

Nadat Willem III in 1702 overleed verslechterde de verhoudingen tussen de Nederlanden en Engeland. De Staatse Vloot moest het na die tijd steeds vaker afleggen tegen de sterk groeiende zeemachten van Groot-Brittannië en Frankrijk. Na de Vierde Engels-Nederlandse Oorlog (1780-1784), werd bij de Vrede van Parijs deze neergang van de Nederlanden op zee vastgelegd. Toen in 1792 de Eerste Coalitieoorlog uitbrak, trokken Franse troepen de Nederlanden binnen. De staat van het Nederlandse Leger en de vloot was dusdanig dat zij weinig tegen de Fransen konden uitrichten. Hier kwam nog bij dat binnen de Nederlanden de weerstand tegen het Huis van Oranje dusdanig was gegroeid dat de Bataafse Opstand ontstond. Deze door de Franse Revolutie geïnspireerde opstandelingen kozen de kant van de Fransen. In de strenge winter van 1794-1795 lag het grootste gedeelte van de Staatse Vloot vast in het ijs van de bevroren Nieuwediep bij Den Helder. Zonder weerstand te bieden gaf de vloot zich over aan de Fransen. Onder druk van de Fransen werd in de Bataafse Republiek, die hierna ontstond, een centraal Comité van Zeevaartzaken gevestigd en de diverse Admiraliteiten opgeheven. De vloot, nu Bataafse Vloot, werd vanaf dat moment centraal aangestuurd. Nadat Frankrijk de Bataafse Republiek had ingelijfd werd de Bataafse Vloot integraal onderdeel van de Franse marine tot in 1813 het Koninkrijk der Nederlanden werd opgericht.

Na de oprichting van het Koninkrijk der Nederlanden in 1813, werd op 7 december 181 Joan Cornelis van der Hoop aangesteld als Commissaris-generaal en later benoemd tot Minister van Marine. Hiermee werd formeel de oprichting van de Koninklijke Nederlandse Zeemacht vastgelegd.

Een belangrijke ontwikkeling in de modernisering van de Koninklijke Nederlandse Zeemacht vormde de invoering van het Ramtorenschip. Dit werd in Nederland in 1868 ingeluid met de in dienststelling van de Zr. Ms. Schorpioen. Deze stalen schepen kenmerkten zich door het ontbreken van zeilen en de aanwezigheid van een ramsteven. Vanaf de eeuwwisseling begon de ontwikkeling bij Nederlandse marineschepen echter achter te lopen op de Internationale ontwikkelingen. In 1905 werd de Koninklijke Nederlandse Zeemacht omgevormd tot Koninklijke Marine en op 21 december 1906 werd de onderzeedienst opgericht. In Nederland werd vooral geconcentreerd op een reeks kleine scheepstypen zoals monitoren en kanonneerboten ter ondersteuning van troepen aan land. De voornaamste bezigheden en aanwezigheid van grotere oppervlakteschepen vonden plaats in Nederland-Indië waar het Auxiliair Eskader de aanwezigheid van de Koninklijke Marine aldaar bepaalde. In 1917 werd de Marineluchtvaartdienst opgericht en per 1 september 1928 ging het Ministerie van Marine op in een Ministerie van Defensie.

Pas in de jaren 1930 ontstond de noodzaak te komen tot een zeker modernisering van de Koninklijke Marine. Dit plan, het Vlootplan Dekkers, was echter nog volop in ontwikkeling toen de Tweede Wereldoorlog uitbrak. Zowel tegen de Duitsers als tegen Japan moest Nederland het in militair opzicht afleggen, waarna Nederland en Nederlands-Indië bezet werden. Een groot deel van de Nederlandse oppervlaktevloot ging verloren bij de strijd om Nederlands-Indië, wat nog behouden kon worden werd ingezet ten behoeve van de Geallieerden. In Londen werd een Ministerie van Marine ingesteld en op Ceylon en in Australië werden hoofdkwartieren ingericht. Een andere ontwikkeling die tijdens de Tweede Wereldoorlog haar intrede deed was het in dienst nemen van vrouwen bij de marine. Deze werden wel in een eigen organisatie, de Marine Vrouwenafdeling (Marva) ondergebracht.

Na de Tweede Wereldoorlog verschoof de inzet van de Koninklijke Marine van de Indische Archipel naar de Atlantische oceaan. Van een zelfstandige opstelling, nog van belang voor de onafhankelijkheidsstrijd met Indonesië en de oorlog met Indonesië om Nieuw-Guinea, werd overgegaan naar een opstelling in het kader van samenwerking binnen de Verenigde Naties (Korea Oorlog), de West Europese Unie en de NAVO (Koude Oorlog). Aanvankelijk werd een vloot opgebouwd rondom een klein vliegdekschip, de Hr. Ms. Karel Doorman. Door de verschuiving van aandacht van het Verre Oosten naar Europa en de Atlantische Oceaan, raakte dit concept achterhaald. Van groter belang werd het beschermen van scheepvaartroutes en de onderzeebootbestrijding. Ook de samenwerking in NAVO verband werd steeds belangrijker, waarbij ook de afstemming op wapenaanschaf en aanschaf van materieel belangrijker werd. Een belangrijk onderdeel van de samenwerking op maritiem gebied is die met België op het vlak van fregatten en mijnenvegers.

Tegenwoordig is de functie van de Koninklijke Marine tweeledig en wel deelname aan de bescherming van het Koninkrijk en het bondgenootschappelijk grondgebied. Hiertoe heeft Nederland zich verplicht tot de minimale inzet van een Maritieme Taskforce in NAVO verband van vijf schepen en de inzet van mariniers en voor het Koninkrijk inzet bij Nederland en de Cariben.

Kort voor het uitbreken van de Tweede Wereldoorlog werd het bevel over de Koninklijke Marine belegd bij de Bevelhebber der Zeestrijdkrachten (BDZ), die leiding gaf aan Commandant der Zeemacht in Nederland, de Commandant der Zeemacht in het Caribisch Gebied, de Commandant der Zeemacht in Nederlands-Indië en de Commandant van het Korps Mariniers. De BDZ was in die tijd tevens de Chef van de Marinestaf. In 2005 werd deze structuur gewijzigd in een structuur zoals deze in de gehele krijgsmacht werd ingevoerd. Hierbij werd met name de rol van de Chef van de Defensiestaf groter en werd Commandant der Strijdkrachten met rechtstreeks bevel aan de krijgsmachtonderdelen. Operationeel werd vanaf dat moment de Koninklijke Marine aangestuurd door het Commando Zeestrijdkrachten (CZSK), gevestigd in Den Helder. Het Commando Zeestrijdkrachten kreeg de leiding over de Commandant der Zeemacht in het Caribisch Gebied (CZMCARIB), Directie Operaties (DOPS), Directie Materieel Instandhouding (DMI), Directie Personeel Bedrijfsvoering (DPBV).