Информация о дате и месте рождения Андрея Шадры неизвестна, также неизвестно его социальное происхождение. Неясно, родился ли он в городе Дон или позже переехал туда. В записях истории Андрей Шадра впервые упоминается в 1554 году, когда русские войска начали поход против Астраханского ханства.
После того, как войска Ивана Васильевича захватили Казанское ханство в 1552 году, наступила очередь на Астраханское ханство. В октябре 1553 года делегация ногайцев прибыла в Москву с просьбой вмешаться в конфликт с астраханским ханом Ямгурчи, который постоянно нападал на соседей. Ногайцы обещали подчиниться воле государя в обмен на защиту. Захват Астрахани дал бы царю контроль над всей Волгой и важными водными путями торговли.
В апреле 1554 года в поход на Астрахань отправился отряд русских войск, возглавляемый князем Юрием Пронским-Шемякиным и постельничим Игнатием Вешняковым. Он состоял из 30 тысяч человек, а позже был усилен вятскими служивыми людьми под командованием князя Александра Вяземского. Казаки, узнав об этом походе, решили присоединиться к русской армии.
Андрей Шадра и другие атаманы казачьих отрядов с Дона вошли в передовой отряд русской армии под командованием князя Вяземского. Когда войска приблизились к Черному острову, они столкнулись с отрядом татар, возглавляемым астраханским ханом Ямгурчеем. В результате сражения казаки одержали победу, разгромив татар. Некоторые татары попытались бежать в Астрахань, другие ушли в степь, а третья часть двинулась в сторону Азова.
Хан Ямгурчи со своими главными силами отошел и расположился ниже Астрахани. Князь Пронский-Шемякин продолжил движение на Астрахань, а князь Вяземский получил приказ атаковать оставшуюся армию хана Ямгурчея. Астрахань пала без сопротивления, так как татары, которые ее защищали, предпочли бежать. Хан также избежал встречи со своим противником и ушел в Азов вместе с небольшим отрядом верных воинов. Он также отправил своих жен и детей, а также часть ценных вещей путем водного пути вниз по реке в сторону Каспия. Однако казачьему атаману Федору Павлову удалось перехватить ханский конвой в районе Бязцыж-Мачака и пленить жен и детей хана.
Войска Александра Вяземского и донских казаков Андрея Шадры против бегущего хана Ямгурчи продолжалась до границ Азова. В этой войне было очень важно участие донских казаков, которые играли немаловажную роль в разгроме и преследовании хана. Вместе с войсками Юрия Пронского-Шемякина, князь Вяземский прибыл в Астрахань, где появился новый хан, Дервиш-Али. Ранее Дервиш-Али был ханом Астраханского ханства, но из-за проигрыша в междоусобице он вынужден был бежать на Русь, где под покровительством царских властей жил в Звенигороде. Местное татарское население приняло его в качестве нового правителя, после чего был объявлен указ царя, который предписывал освободить всех русских, находящихся в рабстве, под угрозой смертной казни. Хан Дервиш-Али согласился выплачивать Московскому царю годовую дань в виде денег и рыбы. В случае смерти хана, местным жителям следовало отправить царю соответствующее уведомление, и царь сам назначал нового правителя. Когда Дервиш-Али занял ханский престол, русские воеводы покинули Астрахань, оставив некоторый гарнизон, чтобы наблюдать и оберегать нового хана и стрелецкий голову. Все пленные русские воины, среди которых были жены и дети хана Ямгурчи, были освобождены. Однако хан, в прошлом эмигрант и благодарный Москве, вскоре проявил желание быть полностью самостоятельным от Москвы. Возникли трения между ханом Дервиш-Али и московскими воеводами, особенно после того, как хан смог отразить попытки Ямгурчи вернуться в Астрахань. В поисках большей независимости, Дервиш-Али стал искать поддержку у крымского хана. В это время Москву начали доставлять челобитные и доносы, которые вызывали сомнения и подозрения. В конечном счете, осенью 1555 года произошло открытое столкновение между Дервиш-Али и московским "резидентом" Л. Мансуровым. Весной 1556 года Мансуров прислал гонца в Москву с грамотой, в которой сообщалось об измене Дервиш-Али и нападении хана на отряд Мансурова. В результате нападения было убито 150 человек из 500. Когда к Астрахани приблизились крымские татары, хан решил покинуть город, вытеснив оттуда царский гарнизон. Тогда царь Иван Васильевич отправил на помощь отряд во главе с Иваном Черемисиным, сыном боярским, к которому вскоре присоединились донские казаки Ляпун Филимонова и Андрея Шадры. Совместные силы подошли к Астрахани, но Дервиш-Али также, как и предыдущий хан, быстро потерял свою решимость и бежал в Азов. Царские войска и казаки вошли в Астрахань без сопротивления и привели испуганных жителей к присяге, в результате чего Астрахань стала навсегда принадлежать России. В это же время ногайцы наконец пришли к соглашению и приняли подданство Московского царя. Таким образом, контроль над устьем Волги окончательно перешел к Москве. Атаман Андрей Шадра в последующие годы участвовал в грабежах купеческих караванов на Волге и нападал на Ногайскую орду и их столицу городок Ногайчик. Впоследствии он ушел с Волги и основал городок Андреев на реке Терек, от которого началось развитие гребенского казачества.