Bara 18 år gammal och utan att ha spelat en match på seniornivå reste Nielsen till tyska storklubben Bayern München, där han under två säsonger endast fick sex minuters speltid, innan han åkte hem till Danmark och Odense som hann vann danska cupen med år 1993. Nielsen köptes år 1994 av nybildade FC Köpenhamn, där han snabbt blev en nyckelspelare och utsågs till lagkapten. När FC Köpenhamn hamnade i ekonomiskt obestånd i början av 1995, såg man ingen annan utväg än att sälja honom till rivalen Brøndby IF för att undvika en konkurs.
I Brøndby var med om att vinna danska mästerskapet år 1996. Han utsågs även till Årets fotbollsspelare i Danmark detta år. Senare samma sommar såldes Nielsen till engelska Premier League-klubben Tottenham. Han var kvar i Tottenham under fyra säsonger och blev matchvinnare i finalen i engelska Engelska Ligacupen år 1999. Efter kontroverser med klubbens manager George Graham i början av år 2000, lånades Nielsen ut till Wolverhampton, innan han efter säsongen såldes till Watford, där han var kvar under tre säsonger.
År 2003 återvände Nielsen till Danmark och Herfølge i en roll som spelande assisterande tränare. När chefstränaren Johnny Petersen fick sparken efter en halvsäsong på grund av dåliga resultat utsågs Nielsen till att dela huvudansvaret tillsammans med sin tidigare landslagskammerat Michael Schjønberg.
Allan Nielsen slutade sin aktiva karriär efter säsongen 2003-2004 för att fokusera på tränarjobbet, men när klubben efter säsongen 2004-2005 åkte ut ur danska Superligaen, lämnade han klubben och gav upp proffstränarkarriären. I dag jobbar han på Birkerød Sports College och arrangerar Street Football-events.
Esbjerg, Danmark
