Nilsson värvades som 20-åring från Ovesholms IF i division 6 till Åhus Horna BK i division 2. Snart fick allsvenskaHalmstads BK upp ögonen för honom och han värvades till klubben året efter, inför säsongen 2000. Första året i HBK var han med och tog SM-guld. Nilsson utvecklades snart till en av klubbens viktigaste spelare och en av allsvenskans bästa mittfältare. Han debuterade i landslaget 20 november 2002 i en träningslandskamp mot Tjeckien, i vilken han gjorde två mål.
Nilsson var även med i Sveriges trupp till VM 2006 men fick där ingen speltid. I landslaget fick Nilsson spela antingen högermittfältare, högerback eller vänsterback. I EM 2008 spelade han alla tre matcher på vänsterbacksplatsen.[2]
I april 2009 skrev Nilsson på ett treårskontrakt med danska toppklubben Brøndby.[3]
I Sveriges VM-kvalmatch mot Danmark den 6 juni 2009 på Råsunda gjorde Nilsson ett ödesdigert misstag när han skulle rensa bort ett högerinlägg i straffområdet. Bollen träffade Nilssons vänsterben och hamnade hos dansken Thomas Kahlenberg som fick öppet mål och gjorde 1-0 till Danmark, som blev slutresultatet.
Den 12 oktober 2009 meddelade Nilsson att hans sista match med Sverige skulle bli VM-kvalmatchen mot Albanien den 14 oktober 2009.[4]
Nilssons kontrakt med Brøndby gick ut sista juni 2012 och förlängdes inte. [5]Den 8 augusti 2012 meddelade Nilsson officiellt att han avslutade sin karriär som spelare.[6]