Il club viene fondato nel 1904 come FC Germania Kalk, ma in seguito si fonde con altre squadre e cambia denominazione più volte. Vince però nel 1926 - come VfR Köln 04 rrh.- il titolo della Germania Occidentale; in questo modo il partecipa al campionato nazionale, ma non supera il primo turno.
Nel 1933 il campionato tedesco viene riorganizzato dal regime nazista, e il VfR gioca nella Gauliga Mittelrhein. Ottiene qui due vittorie, nel 1935 e nel 1937, ma anche in questi casi la partecipazione alla fase nazionale è breve. Nel 1943 si registra invece l'unione con il Mülheimer SV 06, anch'esso vincitore per due volte della Mittelrhein. In seguito questo campionato viene frazionato, e il neonato club gioca nella Gauliga Köln-Aachen fino al termine della seconda guerra mondiale.
Nel dopoguerra in Germania tutte le squadre vengono rifondate, e il VfR torna ad unirsi al Mülheimer; nasce così il Rapid Köln, che partecipa brevemente all'Oberliga West. Nel 1957 il Rapid si unisce poi con il Preußen Dellbrück, squadra arrivata alle semifinali nazionali nel 1950, e viene così creato il Viktoria Colonia. La squadra continua a militare nell'Oberliga West, e partecipa anche alla Coppa delle Fiere 1962-1963: viene però eliminata nel primo turno dal Ferencváros.
Il Viktoria rimane in terza serie fino al 1994, anno in cui una nuova unione dà vita al Preußen Köln; il Viktoria Köln nasce invece nuovamente nel 2010, e dal 2012 milita in Regionalliga, ora quarta serie nazionale. Dalla stagione 2019-2020 milita in 3. Liga, chiudendo al 12º posto la prima annata.
