Traoré began his career with Planète Champion in his homeland. He came to prominence whilst playing for Burkina Faso in the 2005 African U-17 Championship, with his performances earning him a one-month trial with English Premier League side Manchester United. He impressed in his trials but was not able to sign for them due to work permit issues. Although he had the option of going on loan to a Belgian club first but also had interest from French Ligue 1 side AJ Auxerre. With the decision of his mother, he joined the French side instead.
On 4 January 2009, he was loaned out to Stade Brest 29 for six months. He returned to AJ Auxerre on 31 June 2009.
Traoré became a central figure in the Auxerre team, with his performances attracting interest from Newcastle United in October 2011. In July 2012, he joined Ligue 1 side FC Lorient after Auxerre were relegated to Ligue 2.