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 2002 i en träningslandskamp mot Tjeckien, i vilken han gjorde två mål.
Från och med EM 2004 till och med att Nilsson själv slutade i landslaget höll han oftast en ordinarie plats och fick spela som högermittfältare, högerback och vänsterback. I EM 2008 spelade han alla tre matcher på vänsterbacksplatsen.
I april 2009 skrev Nilsson på ett treårskontrakt med danska toppklubben Brøndby. Nilssons kontrakt med Panathinaikos löpte ut till sommaren och han var därför fri att förhandla med andra klubbar. Innan övergången offentliggjordes spekulerades det i att Nilsson skulle återvända till Allsvenskan och Halmstads BK. Nilssons kontrakt med Brøndby gick ut sista juni 2012 och förlängdes inte.
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.[1] Den 8 augusti 2012 meddelade Nilsson officiellt att han avslutade sin karriär som spelare.[2]