His first club was Septemvri Sofia. Aged 17, he signed with Litex Lovech for a fee of 200 000. After being released from Rodopa Smolyan in January 2008, Todorov signed a 3 year deal with Lokomotiv Plovdiv. He has been given the №17 shirt. Anatoli made his official debut for Lokomotiv in a match against Lokomotiv Sofia on 1 March 2008. The result of which was a 1-2 defeat for Loko Plovdiv. In August 2009 Todorov became part of Lokomotiv Mezdra's squad.