El Fortuna nasqué el 21 de febrer de 1941 després de la fusió de tres clubs locals: Victoria Köln 1911, Bayenthaler SV 1920, i Sparkassen-Verein Köln 1927. D'aquests clubs, el Victoria tenia els millors resultats, havent guanyat un cop la Gauliga Köln-Aachen, durant els anys 40. El Bayenthaler SV 1920 va participar en la Gauliga la temporada 1943-44. L'any 1976, se li uní el club FC Alter Markt Köln.
El Fortuna ha estat un club que majoritàriament ha jugat a la segona divisió, amb moments àlgids com l'ascens a la Bundesliga el 1974 i el sots campionat de copa de 1983. En aquesta competició eliminà successivament SC Freiburg, SSV Ulm 1846, els equips de primera Eintracht Braunschweig, Borussia Mönchengladbach, i Borussia Dortmund per 5 a 0 a les semifinals. La final la disputà enfront del seu rival ciutadà 1. FC Köln, el primer derbi en una final. El Fortuna va perdre per 0-1 amb un gol de Pierre Littbarski. El 1986 va estar a prop d'ascendir novament a la Bundesliga, però fou derrotat pel Borussia Dortmund en el partit de promoció.
A nivell directiu, des de 1967, el club fou presidit pel milionari Jean Löring. Amb la renúncia d'aquest el 2000, el club passà problemes econòmics que el forçaren a deixar la lliga el 2005. Des de 2008 el club és propietat de deinfussballclub.de.[1]
