Poulsen debuteerde in het seizoen 2001/02 in het betaald voetbal bij Esbjerg fB. Daarvoor speelde hij in vijf jaar 104 competitiewedstrijden en trof hij daarin 19 keer het doel. Op 28 januari 2006 kocht sc Heerenveen de Deen voor € 700.000.- en gaf hem een contract voor 3,5 jaar. Hij werd gehaald als vervanger voor Said Bakkati, die naar ADO Den Haag was verkast. In de laatste helft van het seizoen 2005/2006 speelde Poulsen zeven wedstrijden voor sc Heerenveen, In het volledige seizoen 2006/2007 23, inclusief KNVB beker en UEFA Cup. Ondanks dertig competitieoptredens in 2007/08 kreeg Poulsen in de aanloop naar het daaropvolgende seizoen te horen gekregen dat er voor hem geen ruimte meer was in de selectie. Hierop reisde hij af naar zijn vaderland om daar een contract voor vier jaar te ondertekenen bij Aarhus GF.
Bondscoach Morten Olsen liet Poulsen op 11 februari2009 in de wedstrijd tegen Griekenland debuteren in het Deense nationale A-team. Daarmee kwalificeerde hij zich vervolgens voor het WK 2010, waar Olsen hem ook mee naartoe nam. Poulsen maakte daar zijn eerste speelminuten in de tweede groepswedstrijd tegen Kameroen (1-2 winst), toen hij in de 86e minuut inviel voor Jon Dahl Tomasson. In Denemarkens derde en laatste wedstrijd tegen Japan (1-3 verlies) verving hij Martin Jørgensen in de 34e minuut.