Його служба продовжилася на Дону в загоні імені М. В. Крівошликова, потім в батальйоні частин особливого призначення Таганрога. Як одного з кращих червоноармійців, в 1922 році його направили на навчання - спочатку на Кримські кавалерійські курси імені ВЦВК, а потім в Таганрозький кавалерійську школу Північно-Кавказького військового округу (ПКВО). У 1924 р знову навчання - спочатку курсантом, потім старшиною ескадрону Північно-Кавказької горянської національної кавалерійської школи СКВО. Навчання в кавалерійської школі неодноразово переривалася - Гречко брав участь в бойових діях проти банд Махно і Марусі на Україні, потім в Чечні і Дагестані.
У 1926 р після закінчення кавшколи Андрій Гречко призначається командиром взводу, потім кулеметного ескадрону 61-го кавалерійського полку 1-ї Особливою кавалерійської бригади імені товариша І. В. Сталіна Московського військового округу. В атестації 1930 року на А. А. Гречко командир полку Н. М. Дрейер відзначав: «Має силою волі, знаннями, вимогливий до підлеглих ... Справою цікавиться. Працює над собою по ... своєї військової і загальноосвітньої підготовки ». Працьовитість і намагання молодого командира було помічено, і в 1932 році він стає слухачем Військової академії імені М. В. Фрунзе, після закінчення якої в 1936 р призначається в штаб Особливою Червонопрапорної кавалерійської дивізії Московського військового округу.
Капітан А.А. Гречко. 1936 р
У травні 1938 року він призначається командиром 62-го кавалерійського полку, потім помічником начальника штабу і, нарешті, начальником штабу Особливою Червонопрапорної кавалерійської дивізії імені тов. І.В. Сталіна Білоруського військового округу. У 1939 р брав участь в поході Червоної Армії в західні області Білорусії. У 1939 р він стає слухачем Військової академії Генерального штабу імені К. Є. Ворошилова, яку закінчив в 1941 р
Як згадував Маршал Радянського Союзу В. Куликов: «З особливою силою розкрилися видатні організаторські здібності і полководницький талант А. А. Гречко в героїчну битву за Кавказ. Керовані ним війська проявили стійкість і мужність, завдавши нищівних ударів по ворогу. ... У всіх операціях, якими керував генерал Гречко, незмінно виявлялися сміливість його задумів, непохитна воля до їх здійснення, особиста хоробрість ».
Командувач 56-ю армією генерал-лейтенант А. А. Гречко (4-й праворуч) серед офіцерів і генералів 11-го гвардійського корпусу. 1943 р
Командувач 1-ою гвардійською армією генерал-полковник А.А. Гречко (в центрі) з офіцерами штабу армії на лінії Арпада (Східні Карпати). 1944 р
А. А. Гречко в 1945 р
Заслуги генерала А. А. Гречко в роки війни були відзначені високими нагородами - орденом Леніна, 2 орденами Червоного Прапора, орденами Суворова 1-й і 2-го ступеня, Богдана Хмельницького 1-го ступеня, Кутузова 1-го ступеня. Ці нагороди отримували ті воєначальники і командири, які показали «видатні успіхи в справі управління військами, відмінну організацію бойових операцій і проявлені при цьому рішучість і наполегливість в їх проведенні». Маршал Радянського Союзу Г.К. Жуков у своїх спогадах зазначав, що Верховний Головнокомандувач І.В. Сталін з командуючих арміями найталановитішими вважав генералів А. А. Гречко та К. С. Москаленко.
Після закінчення війни Андрій Антонович командував військами Київського військового округу. Гречко проводив рішення Верховної Ради СРСР по демобілізації старших вікових груп особового складу; великі оргмеропріятія по реорганізації військ, політичних органів і штабів стосовно до вимог мирного часу. Визначалися місця постійної дислокації військ, створювалася навчально-матеріальна база, будувалися парки, склади, житло для офіцерського складу, в частинах і підрозділах були організовані заняття з бойової та політичної підготовки. Воїни Київського округу надавали суттєву допомогу у відбудові народного господарства країни: брали участь в розмінуванні, розчищали вулиці в містах і селищах від завалів, відновлювали житлові будинки, підприємства, шахти, культурно-освітні установи, будували мости, забезпечували подачу електроенергії, відновлювали водопостачання і т. д. У 1947-1953 рр. під керівництвом Гречко війська округу провели ряд великих навчань, освоювали нове озброєння.
Головнокомандувач ГСВГ А. А. Гречко на параді військ ННА НДР. 1956 р
Міністр оборони СРСР А. А. Гречко (3-й зліва) на параді військ ННА НДР. 1974 р
Під керівництвом міністра оборони були прийняті найважливіші документи по підготовці і проведенню операцій. Андрій Антонович прийняв і провів в життя ряд істотних рішень у військовому будівництві. Важливим заходом стало навчання генералів і офіцерів оперативно-стратегічної ланки на Вищих академічних курсах при Академії Генштабу і Військово-політичної академії. Велике число офіцерів резерву регулярно закликалося на 2 роки з метою накопичення бойового потенціалу кадрів. Було засновано інститут прапорщиків. Радикально змінилася система підготовки сержантів: замість полкових шкіл з їх різнобоєм в програмах, методиці і навчально-матеріальній базі були засновані навчальні дивізії - танкові, механізовані, артилерійські, утворені окружні навчальні центри. У 1970-ті роки на озброєння армії і флоту надійшло повое покоління бойової техніки і зброї.
Найважливіші положення теорії ядерної війни досліджувалися на численних стратегічних навчаннях і іграх. Серед них особливе значення мало проведене в 1970 р міністром оборони стратегічне командно-штабне навчання «Вирішальний удар», на якому було присутнє вище керівництво країни. Вчення проводилося з реальними пусками ракет і при повномасштабному використанні всіх систем управління і всіх без винятку центральних командних пунктів. Радянська Армія проводила навчання «Німан», «Весняний грім», «Схід», «Захід», «Північ», «Океан». Під керівництвом Гречко в 1970-і роки були проведені стратегічні навчання типу «Центр» - з пусками ракет наземного, повітряного і морського базування. Вперше в єдиному комплексі з розгортанням Збройних Сил та їх стратегічним застосуванням у війні вирішувалися питання перекладу народного господарства з мирного на воєнний стан, роботи економіки в «особливій період», оцінювалися масштаби збитку, втрат, визначалися можливі обсяги відновлювальних робіт. Створювалася струнка система оперативно-стратегічних навчань (фронтових, окружних, коаліційних і т.д.) на театрах військових дій. З 1971 р були проведені оперативно-стратегічні навчання ППО, ВПС, ВМФ, в ході яких були відпрацьовані питання управління видами Збройних Сил та родами військ. В результаті бойова міць Радянського Союзу значно зросла. Захід змушений був шукати нові методи боротьби з радянської цивілізації, відмовившись від можливості прямої агресії.
Як зазначав маршал Віктор Куликов: «Якщо подивитися на розвиток і вдосконалення наших Збройних Сил за всю післявоєнну історію, то маршала А.А. Гречко можна з упевненістю назвати військовим реформатором. Першим з таких реформаторів був І. В. Сталін. Багато зробили для Збройних Сил маршали Г. К. Жуков і А.М.. Василевський. У цьому славному ряду стоїть і Андрій Антонович Гречко. Розвиток Збройних Сил та бойової техніки, повсякденне підвищення боєготовності всіх видів озброєння було в центрі його уваги. Міністр оборони не тільки брав участь у керівництві нашої військово-технічної політикою, а й особисто бував на випробуваннях суперсучасних видів бойової техніки, розбирав з генеральними конструкторами детально кожен вид акредитуючої нового зброї. ... В цілому реформування Збройних Сил, обіймаючи посаду міністра оборони СРСР маршала А. А. Гречко проходило успішно, позитивно позначилося на житті і діяльності армії та флоту ».
Гречко з юності відрізнявся фортецею і здоров'ям. Він вів активний спосіб життя, здійснював тривалі пішохідні прогулянки. Вболівальник Гречко за компанію з Леонідом Брежнєвим (маршал і генсек були дружні) часто бував на футбольних і хокейних матчах. Більш того, він був завзятим спортсменом: із задоволенням і добре грав у волейбол і теніс. Цікаво, що Андрій Антонович не тільки сам тримав себе в формі, а й безпосередніх підлеглих привертав до регулярних занять фізичною культурою: в волейбол у нього грали навіть маршали. Незалежно від посад вони двічі в тиждень з'їжджалися рано вранці в Палац важкої атлетики ЦСКА і тренувалися по повній програмі півтори години. Сам Гречко розминався і грав у волейбол разом з усіма, показуючи, так би мовити, на особистому прикладі, що з фізкультурою розлучатися не варто, в якому віці ти б не був.
Маршал Радянського Союзу А. А. Гречко в військах 2-го гвардійського танкового корпусу. 1972 р