В следующем году он был призван в ряды Красной Армии и с весны тридцать восьмого года стал защищать спортивную честь армейского клуба. Григорий Иванович рассчитывал отслужить положенный срок, а демобилизо- вавйшсь, уйти в московский «Спартак», где его с нетерпением ждали. Но судьба потом распорядилась иначе.
Когда команда «Металлург» сойдет с футбольной сцены, у многих выветрится из памяти, что некогда это был довольно сильный клуб, давший нашему футболу не только Федотова, но и Бескова. Некоторые думают, будто армейцы разыскали Федотова в части, и пропускают футбольное становление Федотова в «Металлурге». Другие полагают, будто Федотову повезло, так как на заре своей футбольной карьеры он перешел в более сильную команду, что и повлияло на дальнейший рост его футбольного мастерства. Ничего подобного, в том-то и дело, что Федотов в 1938 году перешел из довольно сильного клуба, каким был тогда «Металлург», в довольно слабый. Это уже при Федотове армейская команда стала представлять собой грозную силу и долгие годы была лидером отечественного футбола. А когда, осенью 1936 года, «Металлург» завоевал право играть в группе «А», команда ЦДКА, заняв в группе «А» последнее место, потеряла это право. Однако специальным постановлением Всесоюзного комитета число участников на 1937 год было увеличено до девяти, и армейцы, таким образом, остались в группе «А». В 1937 году «Металлург» занимает в чемпионате пятое место с соотношением мячей 26:21, а ЦДКА снова занимает последнее место с соотношением мячей 18:43. На следующий год число команд было увеличено до двадцати шести (игры проводились в один круг). Чемпионом тогда стал «Спартак». Команда ЦДКА заняла второе место (в ее составе играл уже Федотов), а «Металлург» с тем же количеством очков занял третье место. Таким образом, Федотов стоял у истоков становления армейской команды.
В 1939 году ЦДКА занимает в чемпионате третье место, в 1940-м - четвертое. В предвоенные годы армейцы ни разу не стали чемпионами и ни разу не завоевали кубок, однако с 1938 года, когда в команде стал играть Григорий Федотов, армейцы прочно вошли в число ведущих команд страны и на протяжении многих лет ниже четвертой ступеньки не спускались. В эти же годы Федотов становится самым популярным футболистом и лидером по числу забитых мячей в чемпионатах страны, с ним конкурировал только Борис Пайчадзе. Накануне войны на счету Федотова было 68 забитых в чемпионатах мячей, у Пайчадзе - 65.
Заслуга Федотоьа состбяла не только в том, что оё забивал много мячей, этого было еще недостаточно, чтобы клуб в течение нескольких сезонов показывал стабильные результаты. Природный ум, изобретательность, тонкое футбольное тактическое чутье позволяли Федотову, как капитану команды и выдающемуся игроку, сплачивать вокруг себя современный игровой ансамбль, тем более что тренера, стоящего на уровне тогдашних возросших требований, в команде ЦДКА до войны так и не появилось. Безусловно, это отрицательно сказывалось на общих результатах команды, но зато развивало творческую инициативу у самих игроков. В 1939 году в команду пришел Алексей Гринин, в 1940-м - Валентин Николаев, они-то потом вместе с Федотовым и составят костяк грозной армейской линии нападения, которая и по сей день считается в нашем футболе эталоном.
Первый матч в армейском коллективе Григорий Федотов запомнил надолго (один из дебютантов сезона - команда «Стахановец» из города Сталино нанесла армейцам поражение со счетом 4:0). В своей книге «Записки футболиста» Григорий Иванович рассказывает и об этом матче: «Почему так случилось? Возвращаясь домой, в Москву, мы еще в вагоне поезда много и горячо спорили, разбирая игру...
Ведь это вовсе не так просто пропустить за 90 минут игры четыре мяча, не вабив ни одного! Значит, какой-то серьезный недостаток есть в игре нашей команды.
Подумав, решили - основная беда в том, что нет у нас на поле взаимопонимания, чувства локтя. Недостаточно сыгрались.
На тренировках стали обращать особое внимание на проведение внезапных и неожиданных комбинаций... Однако чувство неудовлетворенности не проходило. Наконец мы поняли, что все-таки играем не так, как могли бы. Не хватало главного: интересных тактических находок. Хорошо понимая свои задачи на поле, мы не смогли найти нового в тактике игры команды. А это было необходимо. Возросшее мастерство команд требовало перестройки игры, новых, более гибких тактических форм.
Вот по этому руслу и надо было направить усилия коллектива! Тренер сделать этого не сумел. Правильный путь подсказали товарищи по спортивной борьбе на футбольном поле».
В ту пору у нас было немало выдающихся игроков, и тут, вероятно, любой перечень окажется неполным, но именно в игре Федотова воплотились с наибольшей силой, а может, даже в абсолютной степени самые прогрессивные тенденции нового футбола. И прогрессивными эти черты были вовсе не потому, что они были новыми, а потому, что они по-новому раскрывали принципы и содержание коллективной по своей природе игры.