Vilhjálmsson begon zijn carrière in de jeugd van Boltafélag Ísafjarðar, waarna hij in 2004 overstapte naar FH Hafnarfjörður. Voor die club maakte hij in 2006 zijn professionele debuut. Tot 2010 werd hij driemaal landskampioen en wist het team twee keer de bekerfinale te winnen. In januari 2011 maakte de IJslander op huurbasis de overstap naar Colchester United, op dat moment actief in de League One.[1] Vilhjálmsson viel in de maanden januari en februari driemaal in, voor hij begin maart door FH teruggeroepen werd.[2] Na zijn terugkeer speelde de aanvaller nog eenentwintig competitiewedstrijden, waarin hij tien keer doel wist te treffen. In 2012 werd hij voor een jaar verhuurd aan IK Start. Na dat jaar, waarin de club promoveerde naar de Eliteserien, trok de clubleiding de IJslander definitief aan.[3] Op het hoogste niveau scoorde hij in tweeënhalf jaar drieëntwintig keer. In de zomer van 2015 verkaste Vilhjálmsson naar Rosenborg BK, waar hij zijn handtekening zette onder een verbintenis voor de duur van tweeënhalf jaar.[4] Dit contract werd in december 2016 verlengd tot eind 2019.[5] Begin 2019 ging hij naar Vålerenga IF.[6] De IJslander keerde in februari 2021 terug naar zijn vaderland, waar hij opnieuw voor FH Hafnarfjörður ging spelen. Twee jaar later nam Víkingur hem transfervrij over.