«Настала в моей жизни новая пора. Когда я думаю об этом времени сейчас, первое, что вспоминается мне, это крепкая дружба молодежи, пришедшей в солдатское общежитие. Незнакомые прежде, мы сразу нашли общий язык, общие интересы. Общность цели объединила нас… Мы старались быть дисциплинированными солдатами, внимательными слушателями на занятиях. Как когда-то в детстве хорошо становилось на душе от похвалы учителя в школе, так теперь целый день, бывало, ходишь радостным, если скупой на слова командир скажет после строевой учебы или политбеседы: „Неплохо для начала, красноармеец Григорий Федотов!“».
В новом коллективе Федотов сразу стал лидером. В чемпионате-38 он забил 19 мячей, уступив всего один гол лучшему снайперу первенства киевскому динамовцу Макару Гончаренко. С приходом бомбардира прибавил и армейский клуб. ЦДКА финишировал вторым, уступив только московскому «Спартаку». В чемпионатах 1939 и 1940 годов Федотов становился самым метким, забив по 21 мячу.
Григорий, точнее, Григорий Иванович — так молодого футболиста называли даже пожилые болельщики, — вырос в сильнейшего нападающего той поры. Казалось, что в игре для него нет секретов и как ни опекай Федотова, он непременно забьет. Сам же Григорий Иванович объяснял свою результативность исключительно трудолюбием и усердной работой на тренировках:
«Как же мне удавалось забивать мячи? Должен снова сказать, что готовых решений здесь также нет, да и быть не может. Много мне удалось забить мячей, и, пожалуй, все они были забиты в различной обстановке и по-разному. Самое же основное, мне думается, это всё то же умение хорошо видеть игру на поле, понимать, предугадывать развитие игры, действия своих противников и своих партнеров, стараться быть разнообразным в своих атакующих действиях, с тем чтобы к тебе не привыкали „опекуны“. И решительность. Условие важнейшее. Владея хорошей техникой, ударами с обеих ног, пониманием игры, можно всегда найти брешь в защите ворот, обмануть своего „опекуна“, выйти с честью из трудного поединка с вратарем. Конечно, важно быть морально стойким. Ведь действительно очень трудно забить мяч. Всегда немного волнуешься, когда приходит мгновение удара по воротам. Уверенность в себе необходима. Нападающий всегда должен помнить о своей личной ответственности за усилия своего коллектива. Так меня учили, в таком духе воспитывали. Я, бывало, ночью плохо спал после встречи на поле, во время которой допустил ошибку, упустил возможность забить гол. Ворочаешься с боку на бок, думаешь: „Ну как же так все это случилось?.. Ведь мог же ударить по воротам, чего испугался, зачем отдал мяч другому, зачем медлил?“ Пока не поймешь как следует, отчего произошла ошибка, не уснешь. А когда поймешь — урок на будущее. Ошибка не повторится, прочувствовал ее, пережил глубоко».
В 1940 году в жизни Григория Ивановича произошло знаменательное событие — он женился на своей землячке Валентине Ивановне Жарковой. И футбол тут сыграл не последнюю роль — ведь родные братья Валентины Ивановны Василий, Виктор и Георгий играли с Григорием еще за «красноармейцев». Впоследствии они стали известными футболистами, выступали за «Торпедо». Сама Валентина Ивановна тоже была неплохой спортсменкой — увлекалась гимнастикой, играла в волейбол, лучше всех каталась на коньках. И сын Федотовых Владимир, родившийся в 1943 году, также стал спортсменом — нападающим ЦСКА и сборной СССР, впоследствии известным тренером.
Но чемпионский титул армейцам так и не покорился — третье и четвертое места соответственно. Однако вырисовывались контуры будущей «команды лейтенантов» — ЦДКА второй половины сороковых годов.
«В этот период в нашу армейскую команду пришли молодые футболисты — Алексей Гринин, Владимир Никаноров, Валентин Николаев, Александр Прохоров и другие. Все они были значкистами ГТО, и у каждого за плечами оказался пусть еще небольшой, но боевой стаж футбольных поединков в юношеских командах. Владимир Никаноров, молодой силач, кстати сказать, хороший борец, занял место в воротах. Уже на первой тренировке он показал себя замечательным вратарем! Его внешне простая, без всякой рисовки игра была, быть может, не столь эффектна, но зато надежна. Алексей Гринин оказался полезнейшим для коллектива игроком, настоящим правым крайним нападения нового типа. Наше нападение получило хорошее пополнение и в лице Валентина Николаева. Техничный, с огоньком, на редкость работоспособный, с хорошо отработанными ударами с обеих ног, молодой полусредний сразу прочно занял место в нашей пятерке. В защиту пришел Александр Прохоров, цепкий, неутомимый, способный наглухо закрыть любого нападающего… В такой атмосфере постоянных поисков нового рос и формировался и я в числе других молодых футболистов. Пришло время, и я перешел с места левого крайнего в центр нашей пятерки нападающих. Так решили команда и тренер. Не скрою, было приятно, что коллектив доверил мне такое ответственное место. Но сумею ли я оправдать оказанное доверие?»