He was born in the stanitsa of Pashkovskaya (Пашковская, now part of Krasnodar) in Kuban Oblast into a Cossack family. Shkuro graduated from Cossack Sotnya of the Nikolaevsky Cavalry School in 1907 and served in the Kuban Cossack Host. In World War I Shkuro became the commander of a special guerrilla unit which executed several daring raids behind Austrian-Hungarian and German lines. During World War I, Shkuro was promoted to the rank of colonel.
In the spring of 1918, after the establishment of the Bolshevik régime, Shkuro organized an anti-Bolshevik Cossack unit in the area of Batalpashinsk in the Caucasus. In May and June 1918 he raided Stavropol, Yessentuki and Kislovodsk. After officially joining Denikin's White Army, he became the commander of the Kuban Cossacks brigade which soon increased in size and became a division. In May 1919 Shkuro, as a young lieutenant-general, had a whole cavalry corps of Cossacks under his command.
Shkuro, though charismatic and audacious, showed bravery which often bordered on the reckless; he received several wounds, and also acquired a reputation for his cunning. Many in the White Army's high command, however, considered him undisciplined and somewhat of a "loose cannon".
According to Soviet historians his forces (including his chief of staff Yakov Slashchov) were particularly cruel and prone to looting. In contrast, in his memoirs (which Shkuro dictated in 1921) he describes many instances in which he spared the lives of enemies, including even Bolshevik commissars (whom the Whites usually summarily executed). Shkuro claimed that he saved from execution a Red Army battalion of Jewish volunteers taken prisoner by the Whites, and that he spoke out against and prevented pogroms against the Jewish population. When Denikin’s volunteer army took Kiev in August 1919, however, it inflicted a large-scale pogrom on the Jews. Over 20,000 people died in two days of violence. After these events, Supresskin, the representative of the Kharkov Jewish community, spoke to Shkuro, who stated to him bluntly that "Jews will not receive any mercy because they are all Bolsheviks".
Although the White Army general Pyotr Wrangel valued initiative he also demanded discipline from his subordinates. Wrangel ended up disliking Shkuro, and upon reorganizing the army Wrangel did not give him a command position; this prompted Shkuro's resignation. Shkuro claimed that to the detriment of the anti-Bolshevik cause, both Denikin and Wrangel did not sufficiently understand Cossack society, and that as a result some of their decisions alienated the Cossacks — even though the Cossacks in general remained deeply hostile to the policies of the Bolsheviks.
After the defeat of the Whites, Shkuro lived as an exile, primarily in France and Serbia. For the first few years he and a few other Cossack partners, displaying their great horsemanship, performed in circuses as trick riders across Europe. In addition, he continued to conduct anti-Soviet activities. Russian émigré memoirs depict Shkuro as a very lively man who enjoyed social gatherings with plenty of dancing, singing, drinking, and vivid storytelling about times past.
In 1941, Shkuro agreed to be one of the organizers of anti-Soviet Cossack units consisting of White émigrés and Soviet (mostly Cossack) prisoners of war in alliance with Nazi Germany. He, along with many other exiles, hoped that this would lead to the eventual liberation of all Russia from communism. In 1944, Shkuro was placed in command of the "Cossack Reserve", which were primarily deployed in Yugoslavia against Josip Broz Tito's partisans. In 1945, Shkuro was detained by the British forces in Austria and handed over to the Soviet authorities in Operation Keelhaul. The Supreme Court of the USSR sentenced Andrei Shkuro to death. On 17 January 1947, he was executed, together with Pyotr Krasnov, by hanging.