ロシアの貴族アンネンコフ家（ロシア語版）の出身とされる。父は退役軍人だった。
1906年、オデッサ幼年団（幼年学校）、1908年、モスクワ士官学校を卒業。第一次世界大戦に従軍し、1915年～1917年の間、パルチザン支隊長、シベリア・コサック師団パルチザン連隊長を務めた。1918年3月、オムスク近郊のアタマンスカヤで非公式に創設されたシベリア・コサック管区のアタマンに選出される。
事後、白軍運動に身を投じ、部隊と共にオムスクに移り、パルチザン支隊「師団」を創設した。1918年1月、シベリアのシャラポフスカヤに駐屯。同年3月12日、ソビエト当局に対して決起し、3月19日、オムスクを襲撃。この反乱は、5月までに鎮圧され、オムスクは再びボリシェヴィキの手に渡った。チェコ軍団の反乱後、アンネンコフの部隊は勢力を回復し、1918年6月～11月の間、西シベリアでボリシェヴィキと戦った。
1918年8月、スラヴゴロドで蜂起し、ボリシェヴィキを虐殺した。アンネンコフの部隊は、同年10月までウラル戦線で戦い、10月23日、セミレーチエ・コサック軍のアタマンの指揮下に入った。1919年5月、部隊と共にカザフスタンのセミレーチエ地方に移り、同年10月、配下部隊を「アタマン・アンネンコフ・パルチザン師団」に改編した。1919年8月、アレクサンドル・コルチャークにより、独立セミレーチエ軍司令官に任命。
赤軍に敗れた後、1920年5月27日、部隊と共に中国に渡り、ウルムチに駐屯した。だが、中国当局により逮捕され、刑務所に収監されたが、日本とイギリスの助けにより1924年2月に釈放された。
1926年4月7日、馮玉祥に騙されて金銭と引き換えにソ連内務人民委員部（NKVD）の諜報員に引き渡され、ソ連に連れ戻された。取調は1年以上に渡り、「内戦時の残虐行為」により死刑を言い渡された。1927年8月24日、セミパラチンスクにおいて銃殺。
ソ連崩壊後の1999年、 ロシア連邦最高裁判所の軍事委員会はアンネンコフの名誉回復を拒否した。
