Η Φ/Γ ΛΗΜΝΟΣ ναυπηγήθηκε στα ναυπηγεία Koninklijka Maatschappij de Schelde στο Vlissingen της Ολλανδίας, μαζί με την Φ/Γ ΕΛΛΗ, μετά από παραγγελία του Γενικού Επιτελείου Ναυτικού. Η σύμβαση για την απόκτηση του πλοίου υπογράφηκε στην Αθήνα τον Ιούλιο του 1981 και η ύψωση της Ελληνικής σημαίας έγινε στο Vlissingen την 18 η Σεπτεμβρίου 1982, με πρώτο κυβερνήτη τον Αντιπλοίαρχο Ν.Θεμελίδη ΠΝ. Η Φ/Γ ΛΗΜΝΟΣ κατέπλευσε στην Ελλάδα στις 5 Νοεμβρίου 1982 και έκτοτε συμμετέχει ενεργά στις αποστολές του ΑΣ.

Το όνομα ΄΄ΛΗΜΝΟΣ΄΄ δόθηκε σε ανάμνηση της νικηφόρου ναυμαχίας του Ελληνικού Στόλου που διεξήχθη την 5 Ιανουαρίου του 1913, πλησίον των ακτών του ομώνυμου νησιού. Οι νικηφόρες ναυμαχίες (ΕΛΛΗΣ και ΛΗΜΝΟΥ) του Ελληνικού Στόλου υπό τον Ναύαρχο Παύλο Κουντουριώτη, κατά τους Βαλκανικούς Πολέμους, ήταν αυτές που εξασφάλισαν την Ελληνική κυριαρχία στο Αιγαίο. Η Φ/Γ ΛΗΜΝΟΣ είναι το τρίτο διαδοχικά πλοίο του ΠΝ το οποίο φέρνει το όνομα ΄΄ΛΗΜΝΟΣ΄΄. Το πρώτο ήταν το πρώην Αμερικάνικο θωρηκτό MISSISSIPPI το οποίο ναυπηγήθηκε το έτος 1905 και αγοράσθηκε από την Ελληνική Κυβέρνηση το καλοκαίρι του 1914. Έλαβε μέρος στις Ναυτικές Επιχειρήσεις του Ά Παγκοσμίου Πολέμου και στις Επιχειρήσεις στη χερσόνησο της Κριμαίας το 1919. Παροπλίστηκε το 1932. Το δεύτερο ήταν αρματαγωγό, το οποίο παραχωρήθηκε το 1943 από την Αμερικάνικη στην Ελληνική Κυβέρνηση για την ενίσχυση του μαχόμενου κατά τον ΄Β Παγκόσμιο Πόλεμο Ελληνικού Ναυτικού. Συμμετείχε στις αποβάσεις του ΑΝΤΖΙΟ (Ιανουάριος 1944) και Νοτίου Γαλλίας (Αύγουστος 1944). Παροπλίστηκε το 1977.