Aleksandr Anjukov började i en fotbollsskola i Samara när han var sex år gammal. 2000 började han spela för den ryska klubben Krylja Sovetovs ungdomslag i andra divisionen. Anjukov debuterade i Ryska Premier League den 14 oktober 2000 i en match mot Zenit St. Petersburg. Han spelade i Krylja Sovetov fram till mitten av 2005. Under denna tid debuterade han i Rysslands fotbollslandslag. I juli 2005 köptes Anjukov av den ryska storklubben Zenit St. Petersburg.