Как бы ни относиться к вынужденному союзу с кубанскими большевиками, но благодаря ему привлеченный к их военному строительству Шкура получил мандат на формирование казачьих полков, а также возможность беспрепятственно разъезжать по станицам и агитировать казаков за вступление в ряды создаваемой красной кубанской армии. А в случае необходимости всегда легко можно было заставить казаков повернуть оружие против большевиков...
Однако сведения о своевольстве Автономова очень скоро дошли до высшего большевицкого руководства. Он был вызван для «объяснений» в Москву, а на III-м съезде Советов Кубанской и Черноморской Республик его лишили всех занимаемых должностей. Лишь благодаря личному заступничеству Г. К. Орджоникидзе Автономов смог вернуться на Кавказ, чтобы «искупить свою политическую недальновидность» и воевать против белых, но теперь уже в скромной должности командира бронепоезда. Он умер от тифа в январе 1919 года.
Стоило Автономову покинуть Кавказ, как по обвинению в подготовке «контрреволюционного заговора» чекистами был арестован и Шкура. Переведенного во Владикавказскую тюрьму полковника спасло чудо, когда его, перепутав по фамилии с большевиком-матросом, выпустил из тюрьмы один из красных военачальников Беленкевич.
Итак, «степной волк» снова на свободе. Теперь уже не было смысла отказываться от первоначального намерения организации повстанческих отрядов, и подготовка к восстанию пошла полным ходом. Коренным образом изменилась ситуация и на всем Северном Кавказе. Терские казаки, первоначально также не отрицавшие возможности признания Советской власти, были возмущены несправедливостью при разрешении земельного вопроса. Чеченцам и ингушам безвозмездно, под лозунгом «восстановления исторической справедливости», передавались завоеванные кровью казачьи земли, а самих казаков насильно переселяли в Ставропольскую губернию. Таким образом, и Кубанцы, и Терцы были готовы начать борьбу с большевиками при первой же благоприятной возможности.
Бежав из тюрьмы в мае 1918 года, Шкура, опираясь на заранее подготовленные офицерские и казачьи ячейки, сумел быстро сформировать несколько партизанских отрядов, закупить оружие и подготовиться к выступлению. Глухая, окруженная страшными легендами «Волчья поляна» среди гор, в лесу под станицей Бекешевской стала местом сбора повстанцев. Здесь, стоя под своим черным «волчьим» значком, ночью 25 мая 1918 года Шкура зачитал «приказ № 1», которым принимал на себя командование отрядом, состоявшим всего из двух штаб- и пяти обер-офицеров и шести казаков и имевшим на вооружении 4 винтовки, 2 револьвера и 2 бинокля. Правда, через несколько дней арсенал пополнился 200 пиками, 80 шашками и 80 кинжалами. Так началась партизанская война на Кубани...
Вскоре численность отряда выросла до 40 бойцов. Офицеры и казаки призывали к выступлению окрестные станицы: Усть-Джмуринскую, Воровсколесскую, Баталпашинскую, Бекешевскую, Боргустанскую. В Кумско-Лоовском ауле повстанцев поддержали черкесы. Любыми способами, даже перекупкой у красных, доставалось оружие. С большим риском Шкура и его начальник Штаба полковник Я. А. Слащов выступали на станичных сходах, призывая казаков к решительному выступлению против Советов.
О полковнике-партизане стали ходить настоящие легенды. Местный юродивый Георгий ходил по станицам, предрекая скорое появление неуязвимого «воина Андрея», который освободит всю Кубань. Июньскими ночами «волкипартизаны» собирались на сходы, обсуждая новые набеги. При появлении «шкуринцев» в Суворовской 10 июня 1918 года в одночасье поднялась вся станица. Из добровольцев и четырех мобилизованных возрастов казаков быстро сформировали три конные и две пластунские сотни. Возглавил Суворовский отряд есаул Русанов, прошедший позднее с генералом весь его боевой путь. Станичный арсенал передал в распоряжение отряда 800 винтовок и 15 ООО патронов. В Воровсколесскую станицу Шкура также вошел без боя, приняв парад выстроенных на станичной площади казаков. Когда не хватало патронов, повстанцы шли врукопашную, пуская в ход шашки и кинжалы. Центрами сопротивления стали станицы Боргустанская и Бекешевская. Сюда на встречу с казаками приходили делегаты от крестьян Ставропольской губернии.
Восстание, поднятое Шкурой в Баталпашинском отделе, совпало по времени с началом наступления на Кубань Добровольческой Армии - с началом Второго Кубанского похода. Теперь красному Главнокомандующему И. Л. Сорокину приходилось считаться с тем, что у него в тылу разгоралось пламя партизанской борьбы, и перебрасывать на борьбу с повстанцами части с фронта. Вскоре повстанцам пришлось сражаться не только с красными гарнизонами, но и с многочисленными и хорошо вооруженными артиллерией и пулеметами частями.