Η Νέα Σαλαμίνα έδειξε ενδιαφέρον για το άθλημα της πετοσφαίρισης από την ίδρυσή της.[2] Από το 1954, η Νέα Σαλαμίνα διοργάνωνε κάθε καλοκαίρι ερασιτεχνικά πρωταθλήματα και κύπελλα, τα οποία προσέλκυαν πλήθος κόσμου. Στα πρωταθλήματα λάμβαναν μέρος ομάδες της επαρχίας (Νέα Σαλαμίνα, Ανόρθωση, Αναγέννηση Δερύνειας, Μαραθώνας Κάτω Βαρωσίων, ΕΝΑΔ Αγίου Μέμνονος).[3]
Μετά την τουρκική εισβολή, την κατάληψη της Αμμοχώστου το 1974 και τον εκτοπισμό των φιλάθλων του σωματείου στις ελεύθερες πόλεις της Κύπρου, ένας από τους ιδρυτές του σωματείου, ο Νικής Γεωργίου, πρότεινε το 1975 τη δημιουργία πετοσφαιρικής ομάδας στη Λεμεσό, ώστε να διατηρηθεί η οντότητα του σωματείου η οποία απειλείτο μετά την προσφυγιά και το διασκορπισμό των φιλάθλων της ομάδας (η ποδοσφαιρική ομάδα επαναδραστηριοποιήθηκε το 1974 στη Λάρνακα). Στη Λεμεσό υπήρχε και υπάρχει από το 1974 μεγάλο μέρος των φιλάθλων της Νέας Σαλαμίνας.
Η πετοσφαιρική ομάδα ανδρών δημιουργήθηκε το 1976. Αποτελεί ένα από τα 20 ιδρυτικά σωματεία της Κυπριακής Ομοσπονδίας Πετοσφαίρισης (ΚΟΠΕ) το 1978. Στην πρώτη συμμετοχή της στην Α' κατηγορία κατετάγη στη δεύτερη θέση. Την ίδια θέση κατέλαβε το 1981 και το 1983. Το 1981 έχασε το πρωτάθλημα στη διαφορά σετ.[4] Το 1983 κατέκτησε το πρώτο της κύπελλο, κερδίζοντας στον τελικό την Ανόρθωση με 3-1. Ήταν ο πρώτος τελικός που συμμετείχε η πετοσφαιρική ομάδα και το πρώτο τρόπαιο που κατακτούσε το σωματείο σε επίπεδο ανδρών. Την περίοδο 1989-90 κατέκτησε το πρώτο πρωτάθλημα στην ιστορία της. Παράλληλα κατέκτησε και το κύπελλο για δεύτερη φορά. Ακολούθησε ένα ακόμα πρωτάθλημα την επόμενη περίοδο και ένα κύπελλο τη μεθεπόμενη.[1]
Την περίοδο 1998 με 2003 η Νέα Σαλαμίνα κατέκτησε έξι πρωταθλήματα στη σειρά. Αυτή η επίδοση αποτελεί το απόλυτο ρεκόρ στην ιστορία του κυπριακού πρωταθλήματος πετοσφαίρισης. Τα τελευταία τέσσερα πρωταθλήματα ήτανε τρεμπλ καθώς η ομάδα κατέκτησε πρωτάθλημα, κύπελλο και ασπίδα και τα τελευταία πέντε νταμπλ.[1] Προπονητής της ομάδας την περίοδο αυτή ήταν ο Αντώνης Κωνσταντίνου. Συνολικά η πετοσφαιρική ομάδα έχει κατακτήσει 9 πρωταθλήματα, 8 κύπελλα και 8 Σούπερ Καπ (πολυνίκης του θεσμού). Ακόμη ήταν δευτεραθλήτρια 6 φορές και φιναλίστ του κυπέλλου 7 φορές.[1]
Η ομάδα έχει πολλές ευρωπαϊκές συμμετοχές.[5] Μεγαλύτερη επιτυχία της είναι η πρόκριση στις 16 ομάδες του Challenge Cup, επικρατώντας στον κυπριακό εμφύλιο τη συμπολίτισσα Ανόρθωση, με δύο νίκες, την περίοδο 2011-12.[6] Θεωρείται η μεγαλύτερη επιτυχία των κυπριακών ομάδων στα κύπελλα Ευρώπης (την ίδια επιτυχία σημείωσε και η ΑΕΚ Καραβά την ίδια περίοδο).
Σημειώσεις: 1Το παιχνίδι αναβλήθηκε λόγω κακών καιρικών συνθηκών. Η αποστολή της Νέας Σαλαμίνας ταξίδεψε μέχρι το Βουκουρέστι, όμως οι άσχημες καιρικές συνθήκες δεν τους επέτρεψαν να μεταβούν στην Κωνστάντζα για το παιχνίδι. Μετά από διαβουλεύσεις με τις δύο ομάδες και ενημέρωση των ομοσπονδιών πετοσφαίρισης Κύπρου (ΚΟΠΕ) και Ρουμανίας, αποφασίστηκε όπως ισχύσει το αποτέλεσμα του πρώτου αγώνα με την Τομίς να προκρίνεται στην επόμενη φάση. Η Νέα Σαλαμίνα συμφώνησε ώστε να αποφύγει επιπλέον ταλαιπωρία η αποστολή, με την προϋπόθεση ότι θα αποφύγει οποιεσδήποτε κυρώσεις.[49]
Το 1978 αποφασίστηκε η δημιουργία γυναικείας ομάδας πετοσφαίρισης στη Λεμεσό, με στόχο «πρώτο να ασχολούνται οι κοπέλες με το βόλεϊ και δεύτερο να διατηρείται η οντότητα του σωματείου», η οποία απειλείτο μετά την προσφυγιά και το διασκορπισμό των φιλάθλων της ομάδας. Πρώτος προπονητής της ομάδας ήταν ο Νικής Γεωργίου.[56]
Με τη λήξη της περιόδου 1984-85, το διοικητικό συμβούλιο αποφάσισε να αναστείλει τις δραστηριότητες της γυναικείας ομάδας για οικονομικούς λόγους.[56][57] Η Νέα Σαλαμίνα την τελευταία της περίοδο ήταν φιναλίστ του κυπέλλου. Συνολικά, στα 7 χρόνια παρουσίας της, η γυναικεία η ομάδα ήταν τρεις φορές δευτεραθλήτρια (1980-81, 1981-82, 1982-83) και τρεις φορές φιναλίστ του κυπέλλου (1979-80, 1982-83, 1984-85).[58] Μάλιστα, την περίοδο 1981-82 είχε ισοβαθμήσει στην πρώτη θέση με την ΑΕΛ Λεμεσού, αλλά υστερούσε στην αναλογία των σετ, κατά μόλις δύο σετ.[56]
Το 2011 δραστηριοποιήθηκε ξανά το τμήμα της γυναικείας πετόσφαιρας με τη δημιουργία τμημάτων κορασίδων και παγκορασίδων που αγωνίζονται στα αναπτυξιακά πρωταθλήματα της ΚΟΠΕ.
Η Νέα Σαλαμίνα διατηρεί τμήματα πετοσφαίρισης εφήβων (U19), παίδων (U17) και παμπαίδων (U17). Η Νέα Σαλαμίνα είναι η ομάδα με τις περισσότερες κατακτήσεις τίτλων στα πρωταθλήματα υποδομής ανδρών. Η ομάδα εφήβων έχει κερδίσει 9 πρωταθλήματα (πολυνίκης του πρωταθλήματος), οι παίδες 8 πρωταθλήματα (πολυνίκης του πρωταθλήματος) και οι παμπαίδες 7 πρωταθλήματα. Η ομάδα εφήβων έχει κατακτήσει επίσης 6 κύπελλα (πολυνίκης του θεσμού).[59]