H ναυπήγηση της Φ/Γ ΝΑΒΑΡΙΝΟΝ στα ναυπηγεία RΟΥΑL DΕ SCΗΕLDΕ άρχισε την 2 Σεπτεμβρίου 1975 και η καθέλκυση της πραγματοποιήθηκε την 16 Απριλίου 1977. Το πλοίο παρέμεινε στην δύναμη του Ολλανδικού Ναυτικού με το όνομα ΗΜΝLS VΑΝ ΚΙΝSΒΕRGΕΝ (F809) έως το 1993. Η Ελληνική σημαία υψώθηκε στο πλοίο την 1η Μαρτίου 1995 στο Den Helder και το πλοίο κατέπλευσε στην Ελλάδα την 15-05-1995. Το πλοίο ονομάστηκε ΝΑΒΑΡΙΝΟΝ με σκοπό να τιμήσει τη δράση του ενωμένου Βρετανο-Γαλλο-Ρωσικού στόλου ενάντια στον Τουρκο-Aιγυπτιακό στη ναυμαχία του ΝΑΒΑΡΙΝΟΥ που διεξήχθη στις 20 Οκτωβρίου 1827.

Οι συνέπειες αυτής της ναυμαχίας ήταν εξαιρετικά σημαντικές για την εξέλιξη της επανάστασης του 1821 καθώς και για την απελευθέρωση της Ελλάδας Η Φ/Γ ΝΑΒΑΡΙΝΟΝ είναι το τρίτο πλοίο του Πολεμικού Ναυτικού που φέρει αυτό το όνομα. Το πρώτο (C-63) ήταν αντιτορπιλικό τύπου «Ε», πρώην ΗΜS ΕCΗΟ (H23), ναυπηγήθηκε στο Ηνωμένο Βασίλειο το 1933, δανείσθη στο Ελληνικό Ναυτικό την 5η Απριλίου του 1944 στη Μάλτα και επεστράφη στο Βρετανικό Ναυτικό την 8η Μαρτίου του 1956. Το δεύτερο (D-63) ήταν δωρεά του U.S.Ν. Ήταν αντιτορπιλικό τύπου Fletcher, πρώην U.S.S. Brown (DD 546) που κατασκευάσθηκε στις ΗΠΑ το1942. Παρεχωρήθη στις 27 Σεπτεμβρίου 1962 στο Σιάτλ και παρέμεινε στο Ελληνικό Ναυτικό μέχρι τον παροπλισμό του την 31η Οκτωβρίου του 1981.