Møller föddes i en liten stad som heter Abildgård, nära Fredrikshavn och spelade i sina yngre år för Ålborg BK. Han fick sitt genombrott när han gjorde debut för Ålborg 1990 under managern Poul Erik Andreasen. I november samma år tog han sig in i truppen till Danmarks U21-landslag och gjorde där 16 mål på 22 matcher, inklusive OS 1992. Han gjorde seniorlagsdebut i september året efter men tillbringade sina första år som avbytare.
Møller blev Ålborgs interna skyttekung under sina första fyra säsonger hos klubben och var skyttekung för hela ligan två säsonger i rad 1991–1993. Han jagades av de danska topplagen FC Köpenhamn och Brøndby IF men det var de förstnämnda som fick tag i honom och han bytte klubb i juli 1993. Han spelade för klubben i ett år, men fick kämpa hårt för att göra några mål och det slutade med bara åtta mål på 30 matcher, innan han lånades ut till schweiziskaFC Zürich i augusti 1994. När han återvände till Köpenhamn i juni 1995 men ville lämna klubben och gick då till Brøndby IF.
I Brøndby blev han återigen intern skyttekung två år i rad när laget vann Superligaen säsongerna 1995/1996 och 1996/1997. Efter att ha varit utesluten ur landslaget i tre år återinkallades han i augusti 1996 av den nye managern Bo Johansson.
1997 flyttade han till nederländskaPSV Eindhoven, där han dock inte fick stora framgångar. Dock fick han spela för Danmark under VM 1998, där han spelade två matcher och gjorde ett mål mot Nigeria.
Efter VM flyttade han än en gång, den här gången till Real Oviedo i Spanien. Inte heller där nådde han upp till sin gamla form i Danmark och lånades under en tid ut till engelskaFulham och den gamla klubben Brøndby. Än en gång uteslöts han ur landslaget. På sommaren 2001 återvände han till danska ligan och sin gamla klubb FC Köpenhamn, vilket ledde till att Brøndby-fansen blev mycket upprörda och kallade honom helt enkelt för "nummer 32" efter numret på hans tröja. Han hjälpte Köpenhamn att vinna två ligatitlar och danska cupen2004. Efter två års vila från landslaget togs han återigen med av Morten Olsen i mars 2005. Han gjorde två mål i Danmarks 3–0-match mot Kazakstan i kvalet till VM 2006. Han avslutade dock sin karriär i december 2005, sex månader innan kontraktet med Köpenhamn löpte ut, för att bli sportjournalist för Danmarks Radio. Samma år utsågs han till ordförande för danska spelarföreningen, men lämnade över positionen till Thomas Lindrup när han avslutade sin spelarkarriär.