Обдумав все до деталей, Шкура подал рапорт на имя командира 3-го Хоперского полка полковника Труфанова. Он предлагал вышестоящему командованию следующее:
«…Каждый полк дивизии отправляет из своего состава 30–40 храбрейших и опытных казаков, из которых организуется дивизионная партизанская сотня. Она проникает в тылы противника, разрушает там железные дороги, режет телеграфные и телефонные провода, взрывает мосты, сжигает склады и вообще, по мере сил, уничтожает коммуникации и снабжение противника, возбуждает против него местное население, снабжает его оружием и учит технике партизанских действий, а также поддерживает связь с нашим командованием…»
Рассмотрев предложение казачьего офицера, командир корпуса отправил его на рассмотрение Походному атаману казачьих войск великому князю Борису Владимировичу. Его начальник штаба тогда еще полковник А. П. Богаевский, в Гражданской войне – атаман Всевеликого войска Донского, поддержал разумную инициативу офицера-кубанца.
Великий князь откомандировал напористого в осуществлении своей инициативы Андрея Шкуру в могилевскую Ставку Верховного главнокомандующего России полковника гвардии Николая II Романова. Император, ознакомившись с рапортом об организации партизанского отряда, собственноручно начертал на листе: «Быть по сему». Так на Русском фронте Великой мировой войны начиналось армейское партизанство.
Армейское командование быстро исполнило повеление государя. На формирование партизанского отряда ушло два неполных месяца – декабрь 1915 года и январь 1916 года. Он получил название «Кубанского конного отряда особого назначения». Потом к этому названию добавятся еще два слова – «…(войскового) старшины Шкуро».
Численность его равнялась казачьему полку 4-сотенного состава: 600 конных бойцов – казаков и добровольцев из армейских кавалерийских полков (драгунских, гусарских, уланских). Основу отряда составили казаки и офицеры 3-го Хоперского полка. Войсковой старшина Андрей Шкура лично отбирал людей, с которыми ему предстояло «гулять» по вражеским тылам. Было отмечено, что уже в то время казачий офицер отличался известным самоуправством, доставляя немало забот старшим начальникам.
Отряд имел свой значок (флажок), подобный кавалерийскому штандарту. Автором его являлся сам А. Г. Шкура. На черном полотнище была вышита серебром оскаленная волчья голова. Позднее, уже в ходе Гражданской войны, в 1919 году на значке появится надпись: «Вперед. За Единую, Великую Россию». Ее автором являлся все тот же Шкура, теперь Шкуро, уже носивший генеральские погоны.
Но это была еще не вся атрибутика отрядного значка. На вершине древка и к двум свободным концам полотнища крепились волчьи хвосты. Шкуринские партизаны пришивали волчьи хвосты к концам башлыков и к тыльной стороне своих папах, пошитых часто из волчьих шкур. Они действительно стремились изображать из себя на войне волчью стаю. Разведчики отряда даже условные сигналы подавали, имитируя на разные голоса вой волков.
В конце января 1916 года отряд выступил на фронт. Первые рейды на ту сторону принесли боевой успех: на реке Шаре разгрому подвергся штаб австрийского полка. Шкуринские партизаны брали «языков», совершали всякого рода диверсии, вели разведку. Что же касается «организации партизанской борьбы в неприятельских тылах», то здесь успеха не наблюдалось, как писал в своих мемуарах А. Г. Шкуро, «вследствии пассивности и запуганности населения».
Дерзкие действия партизан доставили много тревог неприятельскому командованию. В марте 1916 года отряд совершил глубокий рейд, прорвавшись на 35 верст от линии фронта, разгромив по пути штаб германской дивизии и взяв в плен ее командира. Имя инициатора этого нападения было известно, и немецкое командование обещало за его поимку награду в 60 тысяч рублей. Но поскольку фронт окончательно занял позиционное положение, «работы» у конных партизан стало мало, а спешенная кавалерия стала вести окопную жизнь.
Имя партизана А. Г. Шкуры было, как говорится, «на слуху». Теперь все чаще его фамилия произносилась более благозвучно – Шкуро, к чему он и сам привык, изменив последнюю букву своей подписи. В белых мемуарах о нем писалось часто. Барон П. Н. Врангель в своих «Записках» так отзывался о командире армейского партизанского отряда, больше напоминавшего во фронтовой жизни атамана «казачьей вольницы»:
«…Полковника Шкуро я знал по работе его в Лесистых Карпатах во главе „партизанского отряда“. Это был период увлечения Ставки партизанщиной. Партизанские отряды, формируемые за счет кавалерийских и казачьих полков, действовали на фронте как-то автономно, подчиняясь непосредственно штабу походного атамана. За немногим исключением туда шли, главным образом, худшие элементы офицерства, тяготившиеся почему-либо службой в родных частях. Отряд есаула Шкуро во главе со своим начальником, действуя в районе 18-го корпуса… большей частью болтался в тылу, пьянствовал и грабил, и, наконец, по настоянию командира корпуса генерала Крымова, был с участка корпуса отозван…»