On March 30, 2009, Poulsen was relieved of his duties from the Football Federation of Armenia.
Poulsen took over as the head coach of Tanzania in August 2010 after being appointed by the Tanzanian Football Federation from a short-list of 5 from 59 applicants. After four months in charge of the team, he led Tanzania to victory in the 2010 CECAFA Cup - the first win of the country since 1994. He left Tanzania in May 2012 and was replaced by his fellow Dane and namesake Kim Poulsen.
In August 2013 he became new manager of the Danish lower league club Solrød FC.