Τη χρονιά του 70-71 η Σαλαμίνα ξεκίνησε με 3 νίκες μία ισοπαλία και μία ήττα στους πρώτους πέντε αγώνες αλλά συνέχισε με 4 ήττες για να τερματίσει τελικά ένατη ενώ ήταν και η τελευταία χρονιά του Βαρνάβα που μεταγράφηκε στον Ολυμπιακό Λευκωσίας που αγωνιζόταν στο Ελληνικό Πρωτάθλημα.

Η μετριότητα συνεχίζεται και την περίοδο 71-72 παρά τη πρόσληψη του Γιουγκοσλάβου Μιλοβάνωφ που ίδρυσε και την ακαδημία παίδων. Χαρακτηριστικό αυτής της χρονιάς η αφλογιστία της επίθεσης που πέτυχε μόνο 16 γκολ σε όλο το πρωτάθλημα ενώ αποχωρούν με το κεφάλι ψηλά μετά από 10 χρόνια προσφοράς οι Κοντεάτης και Κότροφος. Σημαντικό το γεγονός ότι πέρασαν δύο χρόνια από τη μεταγραφή του Κουρέα στον Ολυμπιακό Πειραιώς αλλά δεν εισπράχθηκαν ποτέ τα λεφτά της μεταγραφής.

Η βασική 11αδα της χρονιάς. Από αριστερά όρθιοι Μάλος, Άγγελος, Π Φωκκής, Βαρνάβας, Μουσκάλλης, Μιχαλάκης. Κάτω:  Μυρμιδώνης, Κοντεάτης, Κότροφος, Ματσάγκος, Καραολής.

Το 72-73 εγκαινιάσθηκε το μεγάλο κουσούρι της ομάδας, η μάχη για επιβίωση. Για πρώτη φορά μετά από 18 χρόνια ζωής στην Α' κατηγορία της ΚΟΠ, η ομάδα κινδύνευε με υποβιβασμό. Μόλις δύο βαθμοί χώριζαν στο τέλος της χρονιάς τους ερυθρόλευκους από την ομάδα που υποβιβάστηκε αλλά επίσης παρατηρήθηκε το φαινόμενο της νίκης πάνω σε μεγάλους αντιπάλους όπως ο Ολυμπιακός (πρωταγωνιστής τότε) και η Ανόρθωση. Την χρονιά αυτή αποχώρησε ο επιθετικός Ματσάγκος ενώ ο Καραολής μεταγράφηκε στην Ανόρθωση.

Ο αγώνας για τη σωτηρία συνεχίστηκε και την περίοδο 73-74. Ο Μιλοβάνωφ παραιτήθηκε στην 12η αγωνιστική όταν η Σαλαμίνα ήταν στην τελευταία θέση με 7 βαθμούς και την ομάδα ανέλαβε ο Μαυρίκιος Άσπρου. Η ομάδα σώθηκε την υστάτη ενώ παρουσιάστηκαν και κρούσματα 'φατριών' στην ομάδα σύμφωνα με την ομολογία του τότε προέδρου κ. Νικολάου

Από τις 11αδες του 72-73. Πάνω: Αβραάμ, Νικολάου, Μάλος, Λουκάς, Κουγκάς, Φωκκής. Κάτω: Ιωάννου, Ηλίας, Βραχίμης, Θεοφάνους.

1974. ΕΙΣΒΟΛΗ-ΠΡΟΣΦΥΓΙΑ. Στο σωματείο του Άρη Λεμεσού καθορίζεται συνεδρία στις 14 Οκτωβρίου. Η Σαλαμίνα έπρεπε να επαναδραστηριοποιηθεί. Η απόφαση ήταν να μεταφερθεί η Νέα Σαλαμίνα στην Λάρνακα όπου στεγάσθηκε στο οίκημα της ΑΛΚΗΣ.

Το πρωτάθλημα του 74-75 έγινε στα ερείπια της εισβολής και της κατοχής. Η Σαλαμίνα μετά από προβληματισμό δήλωσε συμμετοχή στο πρωτάθλημα με δύο κλιμάκια, ένα στη Λάρνακα με τον Άσπρου και ένα στη Λεμεσό με τον Νική Γεωργίου. Η Σαλαμίνα στάθηκε άνετα στην κατηγόρια με έδρα το ΓΣΖ και με 28 συνολικά ποδοσφαιριστές να χρησιμοποιούνται λόγω των στρατεύσιμων.

Το οίκημα της Νέας Σαλαμίνας τα πρώτα χρόνια στη Λάρνακα, το καφενείο 'Παλιά Σαλαμίνα' του Στέλιου Ζένιου.

Τη περίοδο 75-76 με έδρα το γήπεδο της Αναγέννησης Δερύνειας και με προπονητή τον Κωστάκη Αντωνιάδη και με τους παίκτες διασκορπισμένους σε όλη τη Κύπρο. Στα μισά σχεδόν του πρωταθλήματος αποχωρούν οι Θεοφάνους και Λουκά για το εξωτερικό ενώ ο Κόκος Ιωάννου τραυματίζεται σοβαρά. Ο Μάλος αποχωρεί μετά από 10 χρόνια συνεχούς παρουσίας ενώ επίσης αποχωρεί ο Ανδρέας Μουσκάλλης παρά το νεαρό της ηλικίας του αναλαμβάνοντας το πόστο του εφόρου. Προωθούνται στην ομάδα οι νεαροί Μαντζούρας, Κακούσης και Νούρος και η ομάδα καταλήγει 11η στο πρωτάθλημα που ανακηρύχθηκε ειδικό χωρίς υποβιβασμό.

Η ομάδα του 1975-76. Από αριστερά: Φωκκής, Κουγκάς, Σταύρος, Σιέλλης, Θωμάς, Αλέξης, Κότροφος, Λουκάς, Αντωνιάδης (προπονητής), Μουσκάλλης (έφορος) Κάτω: Αρτέμης, Μωησής, Άγγελος, Θεοφάνους, Μήτσιος, Ηλίας, Φώτης, Λάκης.

Την χρονιά του 76-77 άρχισε μια πορεία προς τα κάτω σε ένα πραγματικό μαραθώνιο αφού οι ομάδες αυξήθηκαν σε 16 και με τα περισσότερα προβλήματα άλυτα και με προπονητή τον Αντωνιάδη και έδρα το ΓΣΖ. Η ομάδα σώθηκε εύκολα αν και δεν πραγματοποίησε καθόλου καλή χρονιά (ξεκαθάρησαν από νωρίς οι αδύναμες ομάδες) τερματίζοντας στην 13η θέση.

Η περίοδος 77-78 αποφασίστηκε η πρόσληψη του Βούλγαρου Σπύρου Ντεπάρσκι στη τεχνική ηγεσία που άρχισε σοβαρή δουλειά στην ομάδα δίνοντας της καινούρια πνοή και νοοτροπία. Ο Ντεπάρσκι μέσα από τη συστηματική του δουλειά δημιούργησε κάποια εξέχοντα ταλέντα  στην 2η ομάδα όπως οι Φλώρος, Μαύρος, Μαραγκός και ο Τερματοφύλακας Χριστάκης. Η ομάδα βελτιώθηκε επιθετικά τερματίζοντας στη 10η θέση και χαρακτηριστική ήταν και η νίκη επί της μόνιμης πρωταθλήτριας Ομόνοιας με 2-1 (η μοναδική της ήττα) στο Δασάκι που ήταν και η έδρα της ομάδας τη χρονιά αυτή.     

Η Νέα Σαλαμίνα το 76. Πάνω: Φωκκής, Κουγκάς, Σταύρος, Σιέλλης, Θωμάς, Αλέξης, Κότροφος, Λουκάς, Αντωνιάδης (προπονητής), Μουσκάλλης (έφορος) Κάτω: Αρτέμης, Μωησής, Άγγελος, Θεοφάνους, Μήτσιος, Ηλίας, Φώτης, Λάκης.

Η περίοδος 78-79 ήταν και η χρονιά του πρώτου υποβιβασμού της Σαλαμίνας. Το ξεκίνημα της χρονιάς δεν προμήνυε με τίποτα τη συνέχεια. Από το πρώτο γύρο η ομάδα μάζεψε αρκετούς βαθμούς με σοβαρή απόσταση από τους δύο τελευταίους. Στο 2ο γύρο άρχισε ένα σερί από ήττες εντός και εκτός έδρας με αποκορύφωμα τις ήττες από τους αντιπάλους για τη σωτηρία Ολυμπιακό και Ευαγόρα στο ΓΣΖ, έδρα της Σαλαμίνας τη χρονιά αυτή. Στη τελευταία αγωνιστική η ομάδα εξαρτιόταν από άλλους αγώνες για τη σωτηρία της. Χαρακτηριστικό είναι το γεγονός πως η Σαλαμίνα έπεσε με 26 βαθμούς και σώθηκαν 5 ομάδες με 27 και δύο με 28. Η Σαλαμίνα αντιμετώπιζε το Παραλίμνι και ήθελε νίκη, ο Ευαγόρας την ήδη Πρωταθλήτρια και αήττητη Ομόνοια στη Πάφο και ο Ολυμπιακός την Αλκή στη Λάρνακα. Ο Ολυμπιακός νίκησε και σώθηκε, η Σαλαμίνα νίκησε με 3-2 ενώ η Ομόνοια έχασε αμαχητί σε ένα αμφισβητούμενο αγώνα από τον Ευαγόρα με 2-0.

Ο υποβιβασμός της Σαλαμίνας πείσμωσε τον Ερυθρόλευκο λαό που στήριξε την ομάδα στους αγώνες της στη Β' κατηγορία σε ολόκληρη τη Κύπρο την περίοδο 79-80. Η Σαλαμίνα πέτυχε 18 νίκες, 6 ισοπαλίες και 2 ήττες με 70 γκολ υπέρ και 14 κατά. Στο τελευταίο παιχνίδι με τον Οθέλλο Αθηαίνου οι ερυθρόλευκοι παίκτες έγιναν αντικείμενο λατρείας από τους χιλιάδες Σαλαμιναίους στο ΓΣΖ όπου έστησαν ένα μεγάλο πανηγύρι για την επιβλητική άνοδο.