The club was formed as on 21 February 1948 through the merger of three local sides: Victoria Köln 1911 (one of two clubs to bear the name), Bayenthaler SV 1920, and Sparkassen-Verein Köln 1927. Of these clubs, Victoria had the best results, winning its way to the first division of the Gauliga Köln-Aachen in 1941 and capturing the division title there the following season. Bayenthaler SV 1920 side also spent a season in the Gauliga in 1943–44 before the division collapsed as war overtook the region. In 1976, SC Fortuna Köln was joined by FC Alter Markt Köln.
Through most of the last four decades Fortuna has played as a second division side. Highlights of the club's history include promotion to the Bundesliga for the 1974 season and an impressive run through the 1983 German Cup. The team took out SC Freiburg in the first round and eked out a win on penalties over SSV Ulm 1846 in their next match. They then eliminated three first division sides in a row: first Eintracht Braunschweig and Borussia Mönchengladbach, before crushing Borussia Dortmund 5:0 in their semi-final match. This put them into the final against hometown rivals 1. FC Köln, the first time the Cup final had come down to a local derby. Although they outplayed their opposition, Fortuna's magic had run out and they lost 0:1 on a late goal from goal scorer Pierre Littbarski.
In 1986, the side came close to a return to the Bundesliga, but was beaten by Borussia Dortmund in the promotion round. Each team had won their home match in a two-game series, which forced a third contest under the rules in effect at the time. Instead of advancing on the strength of away goals, Fortuna was crushed 0:8 by Borussia Dortmund. A handful of seasons later the club avoided relegation to third tier football at the end of the 1991–92 schedule only when division rivals Blau-Weiß 90 Berlin were denied a licence.
One of the key features of Fortuna's history was the presidency of deep-pocketed Jean Löring. Beginning in 1967, the millionaire's support of the club helped them to continue to field competitive sides for much longer than they might otherwise have. In 1982, he even helped out in another way: trained as an electrician, he personally fixed the floodlights when they failed during a match against SV Darmstadt 98 so the game could go on. Löring, who had been an Oberliga player himself with Alemannia Aachen in his younger years, was ousted as president in 2000 and the club soon deteriorated. In 2005 the club failed financially and was forced to withdraw from league play.
Despite insolvency, the club was able to salvage its youth department, one of the largest in Germany with over 500 players on 25 teams, through a fundraising campaign organized by the former chairman Egbert Bischoff that included a benefit game against 1. FC Köln.