Larsens professionele loopbaan begon bij de Deense club Køge BK. In 2001 werd hij verkocht aan Brøndby IF in de SAS Ligaen. Bij Brøndby speelde hij een enkele wedstrijd. Vervolgens speelde Larsen bij BK Frem, Djurgårdens IF, FC Schalke 04 en FC Toulouse. Sinds 2009 speelt Larsen voor MSV Duisburg in de Bundesliga. Hij draagt rugnummer 19. Sinds 31 januari2010 komt Larsen uit voor Feyenoord. Hij komt op huurbasis over van Toulouse[1], waarbij ook een optie tot koop is bedongen. Bij Feyenoord heeft hij rugnummer 24 toebedeeld gekregen. In de zomer van 2011 tekende Larsen een contract bij Aarhus GF. In 2014 zette Larsen een punt achter zijn voetballoopbaan.
Onder leiding van bondscoach Morten Olsen maakte Larsen zijn debuut op 2 juni2005 in de vriendschappelijke wedstrijd tegen Finland (0-1) in Tampere, net als Daniel Agger (Brøndby IF), Allan Jepsen (AaB), Jesper Christiansen (Viborg FF) en Rasmus Würtz (AaB). Sindsdien speelde hij meer dan vijftien interlands. Bondscoach Morten Olsen nam hem onder meer mee naar het WK 2010. Daar maakte hij zijn eerste speelminuten in de derde groepswedstrijd tegen Japan, waarin hij in de 56e minuut Per Krøldrup verving.