Вскоре численность отряда выросла до 40 бойцов. Офицеры и казаки призывали к выступлению окрестные станицы: Усть-Джмуринскую, Воровсколесскую, Баталпашинскую, Бекешевскую, Боргустанскую. В Кумско-Лоовском ауле повстанцев поддержали черкесы. Любыми способами, даже перекупкой у красных, доставалось оружие. С большим риском Шкура и его начальник Штаба полковник Я. А. Слащов выступали на станичных сходах, призывая казаков к решительному выступлению против Советов.
О полковнике-партизане стали ходить настоящие легенды. Местный юродивый Георгий ходил по станицам, предрекая скорое появление неуязвимого «воина Андрея», который освободит всю Кубань. Июньскими ночами «волкипартизаны» собирались на сходы, обсуждая новые набеги. При появлении «шкуринцев» в Суворовской 10 июня 1918 года в одночасье поднялась вся станица. Из добровольцев и четырех мобилизованных возрастов казаков быстро сформировали три конные и две пластунские сотни. Возглавил Суворовский отряд есаул Русанов, прошедший позднее с генералом весь его боевой путь. Станичный арсенал передал в распоряжение отряда 800 винтовок и 15 ООО патронов. В Воровсколесскую станицу Шкура также вошел без боя, приняв парад выстроенных на станичной площади казаков. Когда не хватало патронов, повстанцы шли врукопашную, пуская в ход шашки и кинжалы. Центрами сопротивления стали станицы Боргустанская и Бекешевская. Сюда на встречу с казаками приходили делегаты от крестьян Ставропольской губернии.
Восстание, поднятое Шкурой в Баталпашинском отделе, совпало по времени с началом наступления на Кубань Добровольческой Армии - с началом Второго Кубанского похода. Теперь красному Главнокомандующему И. Л. Сорокину приходилось считаться с тем, что у него в тылу разгоралось пламя партизанской борьбы, и перебрасывать на борьбу с повстанцами части с фронта. Вскоре повстанцам пришлось сражаться не только с красными гарнизонами, но и с многочисленными и хорошо вооруженными артиллерией и пулеметами частями.
Тактика действий шкуринских партизан была простой. Благодаря хорошо налаженной разведке и знанию Баталпашинского отдела они без особого труда занимали станицы. Там восстанавливалось станичное правление, ряды отрада пополнялись за счет добровольцев и мобилизованных новобранцев, и столь же быстро "шкуринцы" уходили, опасаясь серьезных боев. После оставления станиц двигавшиеся следом советские карательные отряды жестоко расправлялись с казаками... По распоряжению Кисловодской ЧК жену полковника взяли в заложницы, а самому ему предложили сдаться. В ответ Шкура заявил: «Если большевики убьют мою жену, то клянусь, что вырежу в свою очередь все семьи комиссаров, которые мне попадутся в руки. Относительно же моей сдачи передайте им, что тысячи казаков доверили мне свои жизни и я не брошу их и оружия не положу...» Решительность партизана, очевидно, отрезвила кисловодских комиссаров.
Постепенно становилось ясным, что крупного боя с красными избежать не удастся. Как писал впоследствии генерал, «необходимо было увеличивать отрад и мобилизовать возможно большие силы в ожидании первого боя, результат которого должен был произвести громадное впечатление на психологию казачества...» И этот бой состоялся 12 июня 1918 года на подступах к станице Бекешевской. Для ее обороны Шкура мобилизовал все население: «...Бок о бок стояли древние старики, вооруженные кремневыми ружьями, с которыми их отцы и деды завоевали Кубань у горцев и татар, а радом - ребята и бабы с рогатинами. С тяжелым сознанием ответственности смотрел я на этих людей, доверившихся мне и поставивших теперь все на карту. Глазами, полными веры, глядели они теперь на меня. Я дал себе слово погибнуть в случае неудачи, чтобы не видеть гибели этих славных поборников свободы казачества...» Бой был скоротечным и жестоким. Наступавшая красная пехота, несмотря на длительную артподготовку, не смогла противостоять бурному натиску перешедших в контратаку партизан. Победа была полной. Узнав о ней, к отряду присоединилось еще несколько сот казаков-добровольцев, а для того, чтобы вооружить внезапно выросший в численности отряд, было принято решение о нападении на Кисловодск, где размещались богатые склады вооружения.
Бронепоезд «Генерал Шкуро», 1919 год.
Что же касается лозунгов, под которыми казаки шли воевать, и политического содержания программы, то они были до крайности простыми и укладывались в два предложения: «Долой Советскую власть» и «Да здравствует Всероссийское Учредительное Собрание». Не составляло большого труда доказать казакам всю порочность власти большевиков, которая не только грозила им постоянными земельными переделами, не только лишала их традиционных прав и привилегий, но и просто грабила и убивала всех несогласных.
В ночь на 13 июня Шкура тремя колоннами повел свой отряд на Кисловодск. В результате дерзкого набега был разгромлен красноармейский гарнизон города, а от расстрела местной ЧК спасли несколько сот заложников. Правда, жены полковника среди них не оказалось. Ей уже удалось бежать из тюрьмы при помощи штаб-ротмистра Борукаева, и до конца сентября она скрывалась в аулах около Нальчика. Пополнив запасы оружия, захватив продовольствие и мануфактуру, Шкура вечером оставил город.
Основные операции продолжались в треугольнике Бекешевская, Боргустанская, Суворовская. Силы отряда росли, не проходило дня, чтобы к восставшим не присоединялись все новые и новые десятки добровольцев. Вскоре из черкесов был сформирован особый конный горский дивизион. Значение своих побед сам Шкура видел в том, что, несмотря на малочисленность и отсутствие вооружения, казаки «били красную армию, страшную только для беззащитных». К концу июня 1918 года отряд вырос уже в целую дивизию трехполкового состава с трехбатальонной пластунской бригадой. По имени старых казачьих полков, укомплектованных жителями этой местности, полки конной дивизии получили названия 1-го и 2-го Хоперских (кубанских) и 1-го Волгского (терского). Пешие батальоны получили наименования 6-го и 12-го Кубанских пластунских и 1-го Терского. Позднее на основе этих подразделений были сформированы знаменитые дивизии 3-го конного «шкуринского» корпуса, командовали которыми его соратники-партизаны. Вместе с ними генерал прошел по дорогам Гражданской войны от Кисловодска до Воронежа.
Слухи о «волках-шкураках» быстро разлетелись по Кубани. Против большевиков поднимались соседние отделы Кубанского Войска. Восстали казаки Лабинского отдела. Одним из центров повстанцев-лабинцев стала станица Прочноокопская, восстававшая против большевиков 28 раз.
В июле со шкуринцами объединились отряды лабинцев - около 5 тысяч бойцов (1-й Лабинский, 1-й Хоперский полки и два пластунских батальона). С получением этих подкреплений Шкура произвел очередные переформирования, образовав 1-ю казачью дивизию из четырех полков - 1-го и 2-го Хоперских, 1-го Лабинского и 1-го Волгского Терского Казачьего Войска. Начальником дивизии был назначен подъесаул Солоцкий (Солодько), один из вождей лабинских повстанцев. Но вместе со строевыми казаками он привел и огромное количество беженцев и обоз почти в 2000 подвод.
Обстановка на фронте продолжала оставаться напряженной. На Баталпашинский отдел надвигались красные отряды под командованием бывшего прапорщика Я. Балахонова. Из Армавира выступила целая стрелковая дивизия красных. А тем временем Добровольческая Армия уже вступила в решающее сражение за овладение узловой станцией Тихорецкая, с захватом которой белые разбивали центр позиции армии Сорокина и могли держать под ударом Екатеринодарское и Ставропольское направления. Шкура должен был решать - либо оставаться в Баталпашинском отделе и продолжать руководить восставшими казаками, организуя партизанские набеги, либо пробиться на соединение с Добровольческой Армией и затем объединенными силами добить красные отряды. Шкура выбрал второй путь. На сходе казаков в Воровсколесской он сказал, что казачьим отрядам нужно еще «сколотиться и поучиться, прежде чем начинать крупные бои, ибо мы пока еще не серьезное войско, а необученный сброд». Несмотря на столь обидные заявления своего командира, большая часть повстанцев пошла за ним на соединение с Добровольцами.
К вечеру 28 июня повстанцы вышли к Ставрополю. Было уже известно, что после овладения Тихорецкой Деникин не пойдет на штурм Ставрополя, а главные силы направит на взятие Екатеринодара. Тем не менее Шкура решил с налета захватить город, «преподнеся» его Деникину. Ставрополь был взят в лучших традициях партизанской войны: красному гарнизону послали телеграмму, в которой заявлялось, что, если город не будет сдан, его обстреляют из тяжелых орудий (которых у партизан не было). Гарнизон оставил город, и 7 июля белые вошли в Ставрополь.
Накануне состоялась первая встреча Андрея Григорьевича с представителем Добровольческой Армии - командиром Кубанской конной бригады полковником П. В. Глазенапом. Сразу же выяснились политические расхождения: Шкура выступал за освобождение от Советской власти под лозунгом Учредительного Собрания, в то время как Добровольческие командиры явно этому лозунгу не сочувствовали. Были очевидны и разногласия между верхами кубанского руководства - Атаманом А. П. Филимоновым, сторонником тесного сотрудничества с Деникиным, и Кубанской Радой, немалая часть депутатов которой стремилась занять «самостийную» позицию, отстаивая ее по всем направлениям - начиная от создания самостоятельной армии и заканчивая признанием полного государственного суверенитета Кубанской Области. Особенно отличались этим депутаты-«черноморцы» (представители Ейского, Таманского, Екатеринодарского и Кавказского отделов Кубанского Войска). «Линейцы», а именно они входили в состав отрядов, которые привел Шкура, напротив, склонялись к союзу с Добровольческой Армией как носительницей идеи восстановления «Единой Неделимой России».
Но позиция самого Андрея Григорьевича и как «линейца», и как человека, абсолютно чуждого политических конфликтов, была прямо высказана им при первом же свидании с Командующим Добровольческой Армией. Деникину Шкура заявил, что «признает власть Добрармии и предоставляет себя в ее распоряжение».