Poulsen was first noticed when he played for Randers FC in the Danish 1st Division, and he prolonged his Randers FC contract in May 2003.
Poulsen blev første gang bemærket, da han spillede for Randers FC i den danske 1. division, og han forlænget sin kontrakt i maj 2003.