Wilhelmssons profcarrière begon Wilhelmsson bij Mjällby AIF in Zweden, waarna hij in Noorwegen twee seizoenen in dienst was van Stabæk IF, alvorens hij na negen optredens in zijn derde seizoen bij de club werd getransfereerd naar RSC Anderlecht. Bij Anderlecht was hij direct een basisspeler en stond hij zijn plaats in de basis slechts zelden af. In juli 2006 maakte hij bekend dat hij naar FC Nantes vertrok. Wilhelmsson had op dat moment net het WK voetbal 2006 met Zweden achter de rug. Hij kwam niet verder dan een plaats op de bank bij FC Nantes. Op 9 januari 2007 raakte bekend dat de Zweed op huurbasis naar AS Roma zou verkassen. Tevens verkreeg de Italiaanse club een optie tot aankoop op de speler. De club lichtte de optie niet en daarom werd de Zweed het seizoen erop tot de winterstop verhuurd aan Bolton. Na de winterstop werd hij verhuurd aan Deportivo La Coruña. Na dit seizoen vertrok hij definitief bij Nantes en ging hij naar Al-Hilal, een club uit Saoedi-Arabië. In juni 2011 werd hij daardoor verhuurd aan Al-Ahli SC. Nadat zijn contract afgelopen was, tekende hij na een stage op 5 september 2012 bij Los Angeles Galaxy.