3 мая 1939 г. в адрес зарубежных полпредств СССР отправлена телеграмма за подписью И. Сталина, что ЦК ВКП(б) удовлетворил просьбу товарища Максима Максимовича Литвинова (настоящее имя Меер-Генох Моисеевич Галлах (Валлах) — Филькенштейн, еврей по национальности) и освободил его от обязанностей наркома иностранных дел. В документе указано, что такое решение принято ввиду серьезного конфликта, возникшего между ним и председателем СНК Молотовым. В действительности же Литвинов, ввиду своей национальности, стал неподходящей фигурой для подписания любого пакта с Германией. Выполнение обязанностей наркома иностранных дел по совместительству было возложено на Молотова.
Сразу же после снятия опального чиновника Наркомат иностранных дел был окружен подразделениями НКВД. Вскоре последовало приказание Сталина: «Очистить синагогу!»
В мае 1939 г. Разведупр стал 5-м управлением НКО и переведен на новый штат (341 военнослужащий и 189 вольнонаемных сотрудников) со сменой всех заместителей и начальников основных подразделений:
— заместитель начальника управления — майор А.В. Васильев (майор вместо корпусного (генерал-лейтенант) или дивизионного (генерал-майор) комиссара — явление, ставшее обычным для РККА с начала 1937 г., когда молодые и энергичные командиры среднего звена (их называли «дикорастущими») быстро делали карьеру, занимая генеральские должности);
— 1-й отдел — агентурная разведка на Западе (6 отделений), начальник майор (затем полковник) Ф.А. Феденко;
— 2-й отдел — агентурная разведка на Востоке (4 отделения), начальник майор (затем полковник А.П. Кисленко);
— 3-й отдел — военно-техническая разведка (6 отделений), начальник военный инженер 1-го ранга А.А. Коновалов;
— 4-й отдел — паспортный (2 отделения), начальник майор (затем полковник) С.Ф. Пивоваров (с июля 1939 г.);
— 5-й отдел — информационный (7 отделений), врид начальника полковник Г.П. Пугачев (с мая 1939 по июль 1940 г.); начальник генерал-майор Н.И. Дубинин — с декабря 1940 г. до января 1941 г., врид начальника полковник В.А. Новобранец — январь — апрель 1941 г., начальник генерал-майор Н.С. Дронов — с апреля 1941 г.; заместитель начальника отдела по Западу полковник Л.А Онянов, начальник немецкого отделения полковник Гусев, сотрудники немецкого отделения полковник Дьяков, майор Скрынников, майор Лукманов, капитан Горценштейн;
— 6-й отдел — приграничная разведка (3 отделения), начальник полковник Т.Ф. Корнеев;
— 7-й отдел — радиоразведка (2 отделения), начальник майор (затем полковник) Ф.П. Малышев;
— 8-й отдел — радиосвязь (4 отделения), начальник военный инженер 1-го ранга И.Н. Артемьев;
— 9-й отдел — шифровальный (4 отделения), начальник майор НА. Филатов (по октябрь 1939 г.), майор Л.С. Пелевин (с октября 1939 г.);
— 10-й отдел — внешних сношений, начальник полковник Г.П. Осетров;
— 11-й отдел — дешифровальный (7 отделений), начальник майор Н.А. Филатов (с октября 1939 г.):
• 1-е отделение — японское, начальник батальонный комиссар И. Калинин,
• 2-е отделение — китайское, начальник капитан Н. Аншуков,
• 3-є отделение — немецкое, начальник капитан Н. Охрименко,
• 4-е отделение — англо-романское, начальник военный техник 1-го ранга Ф. Огарышев,
• 5-е отделение — польско-прибалтийское, начальник капитан Ф. Охрименко,
• 6-е отделение — ближневосточное,
• 7-е отделение — учебное, начальник техник-интендант 1-го ранга Е. Шах;
— специальный отдел «А» — диверсионный (3 отделения), начальник Х.-У.Д. Мамсуров;
— политический отдел, начальник бригадный комиссар И.И. Ильичев;
— общий отдел (3 отделения), начальник майор (затем полковник) М.С. Маслов (с июня 1939 г.);
— отдел кадров (3 отделения), начальник полковник А. Кондратов, его заместитель — бригадный комиссар И.Ф. Туляков (с июня 1939 г.);
— административно-хозяйственный отдел, начальник майор (затем полковник) К.Н. Деревянко;
— отдел военной цензуры, начальник майор И. Пузырев;
— библиотека, начальник военный инженер 3-го ранга Г. Опрышко;
— Центральная школа подготовки командиров (начальников) штабов (должностные лица уровня округов и армий проходили курс обучения по управлению разведкой, в том числе и оперативной агентурной), начальник полковник М.А. Шалин (по июнь 1939 г.), майор П.С. Петров (с октября 1939 г.);
— Курсы усовершенствования комсостава, начальник полковник В.И. Швецов (по сентябрь 1939 г.), полковник Д.И. Гончаров (с сентября 1939 г.);
— НИИ по технике связи, начальник военный инженер 1-го ранга И.С. Кисиленко;
— Институт оперативной техники (16 военнослужащих, 21 вольнонаемный), начальник майор B.C. Четвериков (с декабря 1939 г.).
Прежний 9-й (Монголо-Синьцзянский) отдел стал самостоятельным подразделением Генштаба и получил наименование «отдел специальных заданий», начальник полковой комиссар Н.С. Соркин.
Особенностью этого штата стало создание впервые в центральном органе военной разведки за двадцатилетнюю историю его существования политического отдела. Этому событию предшествовало введение в июне 1938 г. должности помощника начальника управления по политической части.