В июле 1939 года Г. Н. Сафонов перебрался в Москву и приступил к исполнению своих новых обязанностей. С этого времени его карьера резко и стремительно пошла вверх. Принявшись за работу энергично и напористо, он в сжатые сроки сумел значительно улучшить положение дел. В декабре 1939 года новый Прокурор Союза ССР М. И. Панкратьев внес предложение в ЦК ВКП(б) об утверждении Г. Н. Сафонова одним из своих заместителей. Там оно нашло поддержку, и вчерашний районный прокурор в 35-летнем возрасте становится заместителем Прокурора Союза ССР.

Как часто бывает в таких случаях — здесь не обошлось без завистников. Вскоре в ЦК партии стали поступать «сигналы» о том, что у Сафонова, оказывается, не совсем пролетарское происхождение, и что этот факт он якобы скрыл. Действительно, Григорий Николаевич не особенно распространялся в своих анкетах о родственниках, сообщал о них очень скупо. Он писал, в частности, что его отец до революции арендовал мельницу, а потом работал кустарем. О своем деде-лесопромышленнике умолчал, а о дяде сообщал лишь то, что тот занимался торговлей, а о дальнейшей его судьбе ничего не знает.

Начались проверки; в разные концы полетели запросы. Секретарь Ростовского райкома партии Ярославской области Смирнов доложил в ЦК ВКП(б) о том, что отец Сафонова имел кузницу, а дед по линии матери был лесопромышленником и все свое состояние оставил сыну, то есть дяде Сафонова, который погиб на Севере. Написал он и о других родственниках. Единственным «криминалом» оказалось лишь то, что две его тетки были замужем за офицерами старой армии. Сестры Сафонова, Ольга и Людмила, проживали в Ленинграде. Первая из них была медсестрой, а другая находилась на иждивении мужа, работавшего юристом. Третья сестра, Нина, преподавала в Москве. Получив указанные сведения, в ЦК ВКП(б) посчитали проверку завершенной. Для Сафонова она никаких негативных последствий не имела.

В должности заместителя, а затем и первого заместителя Прокурора (Генерального прокурора) Союза ССР Григорий Николаевич Сафонов пробыл около 9 лет. Непосредственно на него было возложено руководство различными подразделениями центрального аппарата, в частности, отделами общего надзора, статистики и учета, управлением по надзору за местами заключения. Он курировал также главные военные прокуратуры железнодорожного транспорта и морского и речного флота. Много внимания уделял работе с кадрами и административно-финансовым вопросам.

Отличительной чертой Григория Николаевича был исключительно высокий профессионализм, особенно наглядно проявившийся в тот период, когда органы прокуратуры возглавлял малокомпетентный в этом деле Бочков. Во многом именно благодаря таким людям, как Сафонов, Прокуратура Союза ССР сумела сохранить в то время свое лицо. В одной из характеристик Сафонова, относящейся к этому периоду, отмечается: «У тов. Сафонова каждый прокурорский работник получает исчерпывающее указание по конкретному служебному вопросу, с которым он к нему обращается, и здесь авторитет тов. Сафонова, в смысле знания прокурорской работы, стоит высоко».

Работа Сафонова положительно оценивалась и в ЦК партии, особенно в трудный для страны период 1941–1945 годов. Именно в это время заметно активизировалась деятельность курируемого Сафоновым отдела общего надзора.

Г. Н. Сафонову приходилось много раз возглавлять бригады Прокуратуры Союза ССР во время проверок в прокуратурах союзных республик. С этой целью он выезжал на Украину, в Латвию и другие места. Григорий Николаевич принимал участие в Нюрнбергском процессе. Он часто выезжал в Нюрнберг, где консультировал группу обвинителей и следователей от Советского Союза.

В партийной характеристике того времени, подготовленной в ЦК ВКП(б), отмечалось, что Сафонов «глубоко и всесторонне знает работу прокуратуры. Работники прокуратуры, обращающиеся к нему за советом по служебным делам, получают от него исчерпывающие, юридически обоснованные ответы и указания… К разрешению конкретных вопросов подходит исключительно вдумчиво, серьезно.