A csapatot 1895-ben alapították, Turnverein Flingern 1895 néven. Sokáig a nyugat-német Bundesliga meghatározó csapata volt, és kétszer nyerték meg a Német kupát (1979, 1980). Bajnokságot a Bundesliga megalakítása előtt harminc évvel, 1933-ban nyertek. A német kupában ez a csapat az egyetlen, amelyik a kupasorozatban egymás után 18 mérkőzést nyert meg. (1978–1981)
A csapat többször letette névjegyét az európai kupasorozatokban, 1974-ben UEFA-kupa résztvevőként, majd 1979-ben a KEK-ben döntőt játszott Bázelben a Barcelona ellen, melyet tizenegyesekkel 3-4 arányban elvesztett.
A csapat többször is kiesett a Bundesligából, legutoljára 2013-ban. A kétezres évek első éveiben a csapat válságban volt, és rövid ideig a negyedosztályban is szerepelt.
Folyamatos pénzügyi problémái miatt többször is megmentők után kellett kutatnia, 2004-ben – a legismertebb esetként – a város híres zenekara, a Die Toten Hosen sietett segítségükre. A zenekar azelőtt sem volt idegen a csapat számára, hisz tagjait a legnagyobb szurkolók között tartják számon.
2008 januárjában a csapatvezetők bejelentették, hogy az idei cél a feljutás a Bundesliga 2-be. Mindez 2009. május 23-án valóra is vált, így a Fortuna tíz év után újra a másodosztályában folytatja a szezont. 2012-ben osztályozót követően tizenhat év után feljutott a Bundesligába, a vezetőedző ekkor Norbert Meier volt. A 2012–13-as Bundesliga szezont követően a 17. helyen végezve visszaestek a másodosztályba. Öt évnyi Bundesliga 2-es szereplést követően, 2018. április 28-án a Dynamo Dresden elleni győzelemmel harcolták ki, hogy újra az élvonalban szerepelhessenek a 2018-19-es idénytől.[1] A szezont a másodosztály élén fejezték be. A vezetőedző Friedhelm Funkel volt, akinek így hatodik alkalommal sikerült feljutnia edzőként, ami rekord.
