В январе 1938 года, когда ежовская и бериевская чистки вывели из строя сотни руководящих военных работников, образовав зияющие бреши в Наркомате обороны, решением ЦК ВКП(б) Ф.Ф. Кузнецова направили на работу в Главное политическое управление Красной армии в качестве заместителя начальника Главпура. Там он служил на должностях: начальника отдела кадров (январь — май 1938), начальника организационно-инструкторского отдела (май — июнь 1938), заместителя начальника Политуправления РККА (с июня 1940-го — Главного управления политической пропаганды Красной армии — ГУПП КА) (июнь 1938 — октябрь 1940), второго заместителя начальника (октябрь 1940 — июнь 1941), начальника ГУПП КА (с июля 1941 года снова — ГПУ КА) (июнь 1941 — июль 1942). По воспоминаниям работников Главпура, разбирая жалобы военнослужащих, он проявил себя как отзывчивый, внимательный начальник, умевший обобщать недостатки, предлагать конструктивные решения.
В 1942 году Ф.Ф. Кузнецов получил назначение в действующую армию членом Военного Совета Воронежского фронта. Незаурядные организаторские способности, умение Кузнецова работать с людьми, требовательность и внимание к нуждам солдат и офицеров, способность видеть главное в гуще событий были замечены приезжавшими на фронт маршалом А.М. Василевским и генералом армии А.И. Антоновым. Работа с партизанскими отрядами в тылу врага входила в задачу политуправления. И здесь Кузнецов показал себя с положительной стороны. Несомненно, это предопределило назначение Ф.Ф. Кузнецова на должность начальника Разведуправления Генерального штаба. В июле — октябре 1942 года Федор Федотович был членом Военного Совета вновь сформированной 60-й армии, которая в составе Воронежского фронта вела оборонительные бои на левом берегу Дона севернее Воронежа. Затем он вошел в состав Военного Совета Воронежского фронта (октябрь 1942 — апрель 1943). Войска фронта сковывали значительные силы противника, не давая им продвинуться в сторону Сталинграда и Кавказа. Наступая под Сталинградом вместе с войсками Юго-Западного фронта, они провели ряд успешных операций, разгромили 8-ю итальянскую армию, освободили Курск, Харьков, Льгов. Однако в марте вынуждены были оставить Харьков и отступить к Северному Донцу, где остановили врага.
В феврале 1943 года Ф.Ф. Кузнецова вызвали на заседание Политбюро, куда были приглашены также маршалы Г. Жуков, А. Василевский, генерал армии А. Антонов. Первым выступил Сталин и, охарактеризовав положение на фронтах, заговорил о необходимости усиления фронтовой разведки, чтобы она могла более эффективно выполнять свои задачи: «По-видимому, — сказал он, — назрела необходимость преобразовать Управление войсковой разведки в Разведывательное управление Генерального штаба, укрепив его организационно, кадрами и материально, выделив ему необходимые технические средства».
После небольшой паузы он продолжил: «Мы здесь посоветовались и решили рекомендовать на должность начальника Разведывательного управления Генерального штаба нашего Кузнецова Федора Федотовича. Он хорошо поработал в свое время в качестве секретаря одного из московских райкомов партии, затем — в центральном аппарате на должности заместителя начальника Главного Политического управления Красной Армии, а недостающий военный опыт приобрел на фронте».
Позднее, всякий раз, рассказывая об этом заседании Политбюро, Федор Федотович делал ударение на словах Сталина «нашего Федора Федотовича Кузнецова», как бы подчеркивая тем самым, что лично известен Верховному Главнокомандующему.
С 19 апреля 1943 по 9 июня 1945 года Кузнецов возглавлял Разведывательное управление ГШ КА, одновременно служил заместителем начальника ГШ КА по разведке. На созданное приказом наркома обороны № 0071 от 19 апреля 1943 года разведуправление возложили: «руководство войсковой и агентурной разведкой фронтов, регулярную информацию о действиях и намерениях врага и проведение дезинформации противника».
В своей книге, написанной многие годы спустя, В. Никольский писал о Кузнецове: «Это был партийный деятель, получивший сразу звание генерала в связи с тем, что занимал пост секретаря одного из московских районов. Человек незаурядных способностей, Кузнецов, несмотря на отсутствие военного образования, быстро усвоил основное, по его мнению, правило разведки: “Не доверяй’". Руководствуясь им, он, опираясь на знающих помощников, сумел быстро наладить работу и завоевать новому управлению авторитет». 29 июля 1944 года ему было присвоено звание генерал-полковника.
После войны, с 9 июня 1945 по сентябрь 1947 года (до образования Комитета информации при Совете министров СССР), Федор Федотович был начальником Главного разведывательного управления ГШ КА, а затем заместителем председателя КИ.