Le club est fondé en 1993[2] en même temps que l'équipe de Saint-Michel United, puisque les deux clubs sont issus de l'équipe du FC Anse aux Pins. Pour sa première saison parmi l'élite, le Red Star manque de peu le titre, devancé à la différence de buts par Saint-Louis FC. L'année suivante, son premier sacre en Coupe des Seychelles s'accompagne d'une nouvelle place sur le podium en championnat. En 1998, cinq ans après sa création, le Red Star est sacré champion des Seychelles, un titre qu'il remporte une seconde fois en 2001. Le club ne parvient plus ensuite à maintenir son niveau et est relégué en deuxième division à l'issue de la saison 2007.
Si le club est une des meilleures formations du pays, il a beaucoup plus de mal à s'imposer en compétitions continentales. Son baptême à ce niveau a lieu lors de l'édition 1996 de la Coupe d'Afrique des vainqueurs de coupe où les Seychellois sont éliminés dès le premier tour par la formation réunionnaise du SS Saint-Louisienne. L'année suivante, le club bénéficie du forfait de ses deux premiers adversaires pour se hisser en huitièmes de finale, où il chute à nouveau face au SS Saint-Louisienne. Les deux clubs se retrouvent une troisième année consécutive, lors du premier tour de la Ligue des champions de la CAF 1999 avec une fois encore un succès pour les Réunionnais. En 2000, l'aventure s'achève dès le premier tour face à l'équipe malgache du FC Djivan, à l'issue des tirs au but. Pour sa dernière participation à la Ligue des champions de la CAF, en 2002, le Red Star est sorti dès le premier tour par l'équipe tanzanienne de Simba Sports Club. La dernière apparition du club en compétition continentale a lieu lors de la Coupe de la confédération 2005, où le club est sèchement éliminé par les Sud-Africains de Supersport United.
