El Fortuna ganó su primera liga en 1994, y en las dos temporadas siguientes ganó sendos dobletes. Hasta 2002 ganó 2 ligas y 3 copas más, y en 2003 llegó a la final de la Copa de Europa tras eliminar al Trondheims-Ørn y al Arsenal LFC. La perdió contra el Umeå IK.
Tras 6 años sin ganar un título, el Fortuna ha ganado tres ligas más entre 2009 y 2014. Desde entonces es un habitual en la Liga de Campeones, sin pasar nunca de los octavos de final.