Επιτέλους τίτλος! Η περίοδος 1989-1990 αποτελεί την πιο πετυχημένη στην ιστορία του σωματείου. Η Νέα Σαλαμίνα κατέκτησε το πρώτο της ποδοσφαιρικό τίτλο, το κύπελλο Κύπρου. Στον τελικό της 9ης Ιουνίου 1990, η Νέα Σαλαμίνα κέρδισε την Ομόνοια με 3-2 στο Τσίρειο στάδιο στη Λεμεσό. Η επιτυχία αυτή πανηγυρίστηκε έντονα από τους φίλους του σωματείου που κατέκλησαν την δυτική κερκίδα του Τσιρείου σταδίου. Την εβδομάδα πριν το τελικό υπήρξε μεγάλη και πρωτοφανής κινητοποίηση ανάμεσα στους φιλάθλους της ομάδας, ακόμα και από το εξωτερικό, που ταξίδεψαν στην Κύπρο αποκλειστικά για να παρευρεθούν σε αυτό το παιχνίδι. Την επιτυχία του κυπέλλου ακολούθησε η κατάκτηση ενός ακόμη τίτλου, αυτού της Ασπίδας Ανεξαρτησίας, στο πρώτο παιχνίδι της περιόδου 1990-91. Η ομάδα κέρδισε τον πρωταθλητή Αποελ με 1-0 και πρόσθεσε ακόμα ένα τίτλο στην τροπαιοθήκη της. Ήταν ο δεύτερος τίτλος στη ιστορία του σωματείου, σε διάστημα μόνο λίγων μηνών.
Ως κυπελλούχος, η Νέα Σαλαμίνα έπαιξε για πρώτη φορά σε ευρωπαϊκά κύπελλα το 1990, όπου αποκλείστηκε από τον πρώτο γύρο του Κυπέλλου Κυπελλούχων Ευρώπης 1990-91 από την Αμπερντίν ΦΚ. Η Αμπερντίν ΦΚ, η οποία είχε κατακτήσει το Κύπελλο Κυπελλούχων Ευρώπης την περίοδο 1982-83 νικώντας στον τελικό τη Ρεάλ Μαδρίτης, ήταν μια πολύ ισχυρή ομάδα. Το πρώτο παιχνίδι έγινε στο Τσίρειο Στάδιο, στις 19 Σεπτεμβρίου 1990, παρουσία 8000 φίλων της ομάδας. Η Νέα Σαλαμίνα ηττήθηκε με 0-2 . Ο επαναληπτικός έγινε στην πόλη Αμπερντίν, στις 3 Οκτωβρίου 1990. Η Νέα Σαλαμίνα έχασε με 3-0.
Την ίδια περίοδο μια μεγάλη ιδέα γίνεται πραγματικότητα. Μετά απο 17 χρόνια μακριά απο την φυσική της έδρα, η Νέα Σαλαμίνα αποκτά το δικό της γήπεδο, το στάδιο Αμμόχωστος, το οποίο αποτελεί μέχρι και σήμερα την έδρα της ομάδας, στο οποίο στεγάζοντε και τα γραφεία του Σωματείου. Αξιοσημείωτο είναι το γεγονός οτι το στάδιο δεν θα μπορούσε να παραδοθεί χωρίς την εθελοντική προσφορά των αφανών εργατών και απλού κόσμου της Νέας Σαλαμίνας που με σκληρή δουλειά βοήθησε στην ολοκλήρωση του έργου σε μόλις 22 μήνες.
Την περίοδο 1992-93 η Νέα Σαλαμίνα διεκδίκησε το πρωτάθλημα με αξιώσεις. Στο τέλος του πρώτου γύρου ήταν πρώτη στη βαθμολογία και στη διάρκεια του πρωταθλήματος βρέθηκε με διαφορά έως και πέντε βαθμούς μπροστά από τους αντιπάλους της. Τελικά περιορίστηκε στην τρίτη θέση και στα ημιτελικά του Κυπέλλου. Την ίδια θέση κατέκτησε και την περίοδο 1994-95, εξασφαλίζοντας τη συμμετοχή της στο Κύπελλο Ιντερτότο του 1995. Την ίδια περίοδο, ο ποδοσφαιριστής της Νέας Σαλαμίνας Πάμπης Αντρέου αναδείχθηκε πρώτος σκόρερ του πρωταθλήματος με 25 τέρματα. Στο Ιντερτότο συμμετείχε και την περίοδο 1997 αν και είχε τερματίσει όγδοη, αφού οι υπόλοιπες ομάδες δεν δήλωσαν ενδιαφέρον για συμμετοχή.
