Еще в детстве Андрей Шкура показал себя прирожденным лидером среди ровесников. Он рос подвижным и упрямым, умевшим постоять за себя человеком. В восемь лет стал ходить в станичную школу. Затем отец отдал его в подготовительный класс Александровского реального училища. В десять лет поступил в 3-й Московский Императора Александра III кадетский корпус. В революционном 1905 году стал одним из зачинщиков «кадетского бунта», вспыхнувшего из-за «неудовлетворительного качества подаваемых котлет», был отчислен из кадетского корпуса, но через месяц прощен и возвращен назад.
Получив строгое отцовское напутствие, Андрей Шкура успешно одолел в стенах кадетского корпуса курс наук и поступил в столичное Николаевское кавалерийское училище, в котором была казачья сотня. Юнкер отличался любовью к верховой езде и джигитовке. В мае 1907 года на плацу в Петергофе он получил из рук императора Николая II выписку из приказа о производстве в первый чин казачьего офицера – в хорунжие.
Первым местом службы для него стал 1-й Уманский полк Кубанского казачьего войска, который дислоцировался в Закавказье, в городе-крепости Карс. Полк относился к числу прославленных в войнах, имел Георгиевское знамя «За отличие в покорении Западного Кавказа в 1864 году» и 12 Георгиевских серебряных труб с надписью: «За защиту Зорского перевала 23 и 24-го июня 1877 года». Хорунжий Андрей Шкура имел все основания гордиться первым местом своей офицерской службы.
От отца он получил напутствие, двух коней и денежную помощь на ближайшее время. Дружная офицерская полковая семья приняла 20-летнего хорунжего в свой круг, и он службой оправдал доверие товарищей по Уманскому полку.
Карс находился на порубежье с Персией, и уманцам не раз приходилось гоняться в горах за ловкими и лихими разбойниками из племен шахсеван, нарушавших границу и грабивших торговые караваны, творившими беспорядки во владениях шаха. За дерзость и храбрость в одной из таких стычек молодой хорунжий заслужил свой первый орден Святого Станислава 3-й степени и признание казаков-уманцев.
На границе с Персией Андрей Шкура пробыл до начала лета 1908 года, когда состоялся приказ о переводе его в «отцовский» 1-й Екатеринодарский кошевого атамана Чепеги полк, которым командовал будущий соратник Шкуры в Гражданской войне полковник Г. Ф. Бабиев. Он стоял в Екатеринодаре, войсковой столице, а совсем рядом находилась родная станица Пашковская. Вскоре хорунжий расстался с «безобразным периодом» жизни и создал семью, его женой стала знакомая с детства Татьяна Потапова, дочь директора народных училищ Ставропольской губернии.
Средства родителей позволили молодоженам совершить свадебное путешествие в Европу. Молодой хорунжий между делом в Германии ознакомился с технологией производства пустотелых кирпичей. По приезде домой он наладил их производство, но из-за отсутствия коммерческой «жилки» дело у него «прогорело». Тогда беспокойный Шкура добился включения себя в состав военной части экспедиции по поиску золотоносных месторождений в Сибири, организованной правительством. Он прибыл в Нерчинский округ, но тут началась мировая война, и офицер быстро, как мог, вернулся в Екатеринодар.
Само собой разумеется, что его первоочередной полк в первые же дни войны отбыл на фронт. Хорунжий Андрей Шкура отправился на войну в составе третьеочередного 3-го Хоперского полка, укомплектованного запасниками. Полк входил в состав 3-го Кавказского армейского корпуса, которым командовал генерал от артиллерии В. А. Ирманов, сражавшегося на Юго-Западном фронте. Был командиром взвода, потом сотни. В боях не раз показывал смелость и смекалку, умение вести за собой казаков.
Шкура отличился уже в первых схватках с венгерской кавалерией в Галиции, будучи пожалован орденом Святой Анны 4-й степени с надписью «За храбрость». За бои в начале ноября первой военной кампании под Радомом удостоился Георгиевского оружия (шашки) и английского ордена Бани. После ранения в ногу и контузии командир полка отправил офицера в город Луцк принимать пополнения. Там он пробыл до весны 1915 года. Вернувшись на фронт, он вновь отличается в боях и получает ранение в живот. За тот бой получает производство в подъесаулы, будучи отправлен на лечение в Екатеринодар. В тот же год получил чин есаула.
Лечение для Андрея Шкуры было временем бездействия в идущей большой войне. Он был начитан по военной истории, и знания партизанских действий казаков в Отечественной войне 1812 года в тылах французов подсказали ему идею, которая сразу же завладела им. В своих «Воспоминаниях белого партизана» А. Г. Шкура писал:
«В обстановке временного отдыха мне пришла в голову идея сформирования партизанского отряда для работы в тылах неприятеля. Дружественное отношение к нам населения, ненавидевшего немцев, лесистая и болотистая местность, наличие в лице казаков хорошего кадра для всякого рода смелых предприятий, – все это в сумме, казалось, давало надежду на успех в партизанской работе…»