Der Traditionsverein SC Columbia XXI wurde im Jahre 1908 im Jedleseer Gasthaus „Wiedermann“ ins Leben gerufen. Im September desselben Jahres wurde der Verein bei der Vereinsbehörde und Fußballverband angemeldet.

Nach Ende des Ersten Weltkrieges konnten die Columbianer einen eigenen Sportplatz erwerben, der allerdings 1964 einem Wohnhaus zum Opfer fiel, sodass der Verein in die Schwarzlackenau umziehen musste. Seit 1927 spielte Columbia XXI um die VAFÖ-Meisterschaft mit traf hierbei unter anderem auf Red Star, Elektra und Gaswerk. Nach der Auflösung des VAFÖ 1934 traten die Columbianer dem Wiener Fußballverband bei, wo sie in unteren Ligen spielten. Nach der Annexion Österreichs durch das Deutsche Reich 1938 kam es zunächst zu einer erzwungen Einstellung des Spielbetriebs, bis eine genehme Vereinsführung aufgestellt wurde.

Nach dem Sieg in der dritten Klasse 1943 konnte Columbia XXI erstmals in seiner Vereinsgeschichte, inmitten des Zweiten Weltkriegs, in die zweite Liga aufsteigen. Nach Kriegsende kam die Glanzzeit der Jedleseer. 1946 und 1947 konnten jeweils der vierte Rang der zweiten Liga erreicht werden. Der Abgang der besten Spieler von Columbia XXI zu größeren Wiener Vereinen wirkt sich jedoch zunehmend negativ auf die Meisterschaftsergebnisse aus. Mit der Einführung der Staatsliga 1950 ist der Zwangsabstieg des Vereins verbunden, der nicht mehr in die zweite Liga zurückkehren konnte. Die Columbianer stürzten bis 1957 in die 1. Klasse B ab und tummelten sich in der Folgezeit in den untersten Wiener Fußballligen.

Erst 1999 gelang wieder die Rückkehr in die viertklassige Wiener Stadtliga. Daraufhin kämpfte der Verein mehrere Saisonen über um den erneuten Aufstieg in die Stadtliga, Wiens höchster Spielklasse, den sie 2008 auch wieder schafften. Im selben Jahr feierten sie auch ihr 100-jähriges Bestehen.

2009 traf der SC Columbia im Rahmen eines Testspiels auf den FC Arsenal London, was für großes mediales Echo gesorgt hat. Vor rund 7.000 Zuschauern verlor Columbia zwar mit 1:7, konnte zunächst aber sogar mit 1:0 in Führung gehen. In der Saison 2009/10 gelang der SC Columbia mit einem 2:0 Auswärtserfolg am vorletzten Spieltag der Wiener Stadtliga bei IC Favoriten der Aufstieg in die Regionalliga Ost.