Спустя полтора года генерал-майор А. А. Шкирко отзывается в Москву, где начинается его служба в Главном управлении командующего внутренними войсками: начальник оперативного управления — заместитель начальника штаба ВВ (15.10.1992–31.03.1993), первый заместитель начальника штаба ВВ, с 18.09.1993 г. — заместитель командующего внутренними войсками.
Во время известных событий осенью 1993 г. в Москве генерал Шкирко участвовал в переговорном процессе между представителями Президента Российской Федерации и бывшего Верховного Совета РФ при посредничестве Патриарха Московского и Всея Руси Алексия II. Выступая 3 октября, он сказал: «…Я бы хотел обратиться, убедительно обратиться к членам согласительной комиссии со следующим. Я, как военный эксперт, могу однозначно сказать, что наличие в государстве двух военных противостоящих организаций приведет неминуемо к гражданской войне. Я, как военный человек, повидавший всего уже достаточно, во всех наших горячих точках с 1985 года, убедительно прошу вас принять решение — не создавать параллельных вооруженных структур.
С 25.02.1995 г. — заместитель командующего внутренними войсками по чрезвычайным ситуациям, с 26.07.1995 г. — начальник штаба внутренних войск — первый заместитель командующего ВВ. После ранения генерала А. А. Романова возглавил Объединенную группировку федеральных сил на территории Чеченской Республики.
Указом Президента Российской Федерации от 28.12.1995 г. генерал-лейтенант А. А. Шкирко назначен заместителем министра внутренних дел РФ — командующим внутренними войсками МВД России.
Анатолий Афанасьевич — боевой генерал. Особенно напряженным был 1996 г. На долю командующего ВВ выпала тяжелая задача. После президентского Указа от 31 марта 1996 г. «О программе урегулирования кризиса в Чеченской Республике», предусматривавшего прекращение боевых операций и вывод федеральных сил из Чечни, боевые действия продолжались из-за постоянных обстрелов, нападений, диверсий боевиков. Даже последующие мирные инициативы Москвы, приезд Б. Ельцина в Грозный не дали положительного результата. Операции возобновились, с 10 июля на территории Чеченской Республики был введен комендантский час.
Переговорный процесс возобновился после 10-дневных августовских боев 1996 г. в Грозном. Комендантом города был тогда назначен генерал-майор В. В. Овчинников.
События на Северном Кавказе не могли заслонить текущей напряженной работы главка. Об этом говорил генерал А. Шкирко в одном из интервью, подытоживая деятельность войск за 1996 г.
Важным событием в жизни войск было установление Указом Президента от 19 марта 1996 г. Дня внутренних войск, отмечаемого ежегодно 27 марта.
В прошлом неоднократные попытки добиться права иметь свой праздник, как это сделано в отношении других войск, не имели успеха. Инициативы по этому вопросу тонули в верхах. На этот раз, благодаря усилиям генерала А. Шкирко, большой поддержке со стороны министра внутренних дел генерала армии А. Куликова, вопрос был разрешен, учитывая, как говорилось в Указе,
При генерале А. Шкирко была завершена передача охраны ИТУ Министерству юстиции. Стал формироваться новый облик войск, наступила пора сосредоточить
Командующий Объединенной группировкой федеральных войск в Чеченской Республике генерал-лейтенант А. А. Шкирко на командном пункте. 24.12.1995 г.