Το Red Club συστάθηκε από μια ομάδα αγνών και πιστών οπαδών της Νέας Σαλαμίνας στην Λεμεσό, την ποδοσφαιρική περίοδο 1996-97. Το όραμα αυτής της κίνησης ήταν να αποκτήσει η κερκίδα της Νέας Σαλαμίνας χρώμα και παλμό, ούτως ώστε να κρατήσει τους νεαρούς οπαδούς της αγαπημένης «Θεάς» κοντά στην Αμμόχωστο. Πολλοί οπαδοί της Νέας Σαλαμίνας ελκύονται από άλλες ομάδες, λόγω της μέτριας πορείας της ομάδας με αποτέλεσμα σημαντικός αριθμός φιλάθλων να χάνονται από τα γήπεδα. Το πρώτο συμβούλιο του Red Club απαρτιζόταν από δέκα άτομα τους Παντελή Κυριάκου, Δημήτρη Φιλιππίδη, Μάριο Αδάμου, Τάσο Κυριάκου, Χρίστο Κλεάνθους, Κυριάκο Κυριάκου, Μιχάλη Μιχαήλ, Νίκο Μανώλο, Πανίκο Προδρόμου και τον Χρίστο Παπαδόπουλος.

Η πρώτη έδρα του συνδέσμου ήταν το σωματείο Καρμιώτισσα στα Πολεμίδια Λεμεσού. Έμβλημα του Red Club είναι ο δράκος (παραμένει ως σήμερα με κάποιες διαφοροποιήσεις) που αποτελεί και τη μασκότ του συνδέσμου, η οποία εμφανίζεται κατά καιρούς στα εντός έδρας παιχνίδια της ομάδας. Το τωρινό έμβλημα του Red Club είναι ο δράκος με τους ολυμπιακούς κύκλους και τη φλόγα από κάτω, για να θυμίζει την αθλητική άμιλλα και το ευ αγωνίζεσθε.

Την χρονιά 2000 λίγο πριν το τελικό με τον Απόλλωνα μια άλλη ομάδα νεαρών αγνών φιλάθλων της Νέας Σαλαμίνας εμφανίζεται στη Λάρνακα με πρωτεργάτη τον Κυριάκο Βασιλείου, η οποία δραστηριοποιείται στην περιοχή Λάρνακας και ελεύθερης Αμμοχώστου. Τα παιδιά είχαν όρεξη για δουλειά και με όραμα μια κατακόκκινη κερκίδα, το Red Club απόκτησε παρουσία στην Λάρνακα και στην ελεύθερη περιοχή Αμμοχώστου. Το σημερινό Red Club λειτουργεί με ένα κεντρικό συμβούλιο και με κλιμάκια σε Λάρνακα, Λεμεσό, ελεύθερη Αμμόχωστο, Αθήνα και Θεσσαλονίκη.

Ως Red Club θεωρούμε ότι όπου υπάρχει η παρουσία της Νέας Σαλαμίνας, τότε πρέπει να υπάρχει και η παρουσία σωστών και πειθαρχημένων οπαδών που να γνωρίζουν την ένδοξη ιστορία του σωματείου και της κατεχόμενης Αμμοχώστου.

Το κεντρικό συμβούλιο στεγάζεται προσωρινά στο στάδιο «Amberia Αμμόχωστος». Βασικός στόχος των οργανωμένων οπαδών της Νέας Σαλαμίνας, Red Club, είναι να καταστεί ο δωδέκατος παίκτης της ομάδα με την δυνατή φωνή του, αλλά πάντοτε μέσα σε αθλητοπρεπή πλαίσια και μακριά από σκηνές βίας. Επιπλέον ο Red Club έχει κι άλλους στόχους, όπως να διαπαιδαγωγεί τα μέλη του στις αρχές της Νέας Σαλαμίνας και του αθλητισμού. Να διοργανώνει εκδηλώσεις προωθώντας το ομαδικό πνεύμα στο σύνδεσμο αλλά και στην ομάδα. Να δίνει δυναμικό παρόν πάνω στην κερκίδα, όπου κι αν αγωνίζεται η κόκκινη «ΘΕΑ».