Klub został założony w 1897 roku przez Jules’a Rimeta w Paryżu pod nazwą Red Star Club Français. Największe sukcesy osiągał przed wybuchem II wojny światowej, gdy wywalczył cztery Puchary Francji, a piąty dołożył w 1942 roku. W rozgrywkach Division 1 Red Star występował w latach 1932-1933, 1934-1938, 1939-1948 (nie liczony jest okres w latach 1940-1944 gdy Francja była okupowana przez Niemcy), 1965-1966, 1967-1973 i 1974-1975. Najlepszym rezultatem Red Star było zajęcie 7. miejsca w sezonie 1946/1947. Do 1999 roku zespół występował w Division 2, jednak z czasem przeżywał kolejne degradacje i w sezonie 2003/2004 grał nawet w VI lidze. W 2015 powrócił do Ligue 2. W 2017 roku spadł z tej ligi, jednak rok później z powrotem do niej awansował.
