Der SC Red Star wurde 1903 in Ottakring gegründet und spielte erfolgreich in der 2. Klasse. Da der Verein über keine eigene Sportstätte verfügte, blieb ihm der Aufstieg in die 1. Klasse jedoch verwehrt. Erst 1913 konnte ein Grundstück beim Ottakringer Friedhof erworben werden, das jedoch bereits ein Jahr später einer Kleingarten anlage weichen musste. Während des Krieges musste der Verein seinen englischen Namen ablegen und nannte sich "SC Rotstern Wien". Nach Kriegsende nahm der Klub seinen alten Namen wieder an, trat 1926 dem Verband der Amateurfußballvereine Österreichs (VAFÖ) bei und wurde einer der führenden Klubs des neuen Verbandes (Gewinn sämtlicher VAFÖ-Cups 1927, Wiener-VAFÖ-Meister 1928). Im selben Jahr fusionierte der Verein mit dem SC Sturm 1914 Wien.

Nach der Auflösung des Arbeitersportverbandes wurde der Verein in die 3. und letzte Klasse eingeteilt und verlor auch seinen erst 1930 erworbenen Sportplatz am Vogelweidplatz. Die folgenden Jahre waren durch Fusionen geprägt, wobei der Vereinsname immer beibehalten wurde.

Nach dem Zweiten Weltkrieg spielte der FC Red Star zumeist in der Wiener Liga. 1974 erfolgte die Fusion mit dem Verein Ober-Sankt-Veit. Im Jahr darauf bezog der Verein den Auto-Platz in der Kendlerstraße 38 in Ottakring, der bis heute als Heimstätte dient. 1998 kam es zur Fusion mit dem SC Janecka-Penzing. Der neue Vereinsname lautet seitdem SC Red Star Penzing. Gegenwärtig spielt der Verein in der Wiener Oberliga A.