In 2002 voetbalde het standaardelftal van de mannen nog op het laagste niveau. Sindsdien beleefde Fjölnir een opmars die zijn hoogtepunt kende in 2007. Door een versoepelde promotieregeling kon het als nummer drie van de 1. deild karla voor het eerst in de geschiedenis stijgen naar de Úrvalsdeild. Men verbleef er twee seizoenen voordat men weer degradeerde naar het tweede niveau. Sindsdien pendelt de club tussen de eerste en tweede klasse.
In 2016 werd het beste resultaat uit de clubhistorie behaald toen het als vierde eindigde in de eindrangschikking van de Úrvalsdeild.