Fondé en 1945[3], le club domine le championnat local, qu'il a remporté plus que tout autre équipe. Avant l'indépendance de l'Érythrée en 1993, il participe aux compétitions en Éthiopie. Il remporte dans les années 1980 deux Coupes d'Éthiopie. Cette mainmise sur le football érythréen permet à Red Sea de fournir une majorité de joueurs à l'équipe nationale.
Les nombreux succès du club en championnat ou en Coupe nationale l'ont conduit à participer à plusieurs reprises aux compétitions continentales, sans beaucoup de succès. En 1998, il devient le premier club érythréen à participer à la Coupe des Coupes. Ce baptême continental se passe bien avec l'élimination des Éthiopiens de Wolaita Tussa puis du club égyptien d'Ismaily SC. En huitièmes de finale, le CD Costa do Sol du Mozambique met un terme à l'aventure de Red Sea.
Les campagnes en Ligue des champions de la CAF de 1999, 2000, 2003 et 2006 se sont souvent soldées par des éliminations dès le premier tour. En 2001, il parvient à passer un tour en éliminant la formation tchadienne du Tourbillon FC avant de tomber face au futur vainqueur, Al Ahly.
Le club a participé au tournoi régional de la CECAFA. En tant que champion d'Érythrée, il dispute à plusieurs reprises la compétition, parvenant à atteindre les quarts de finale, en 2003 et 2011. Cette dernière participation au tournoi en Tanzanie a également entraîné de nombreuses fuites du pays de la part des joueurs, puisque treize d'entre eux ont demandé l'asile politique à l'issue de la compétition[4].
