O awansie Nikołaja Jeżowa na wakujące stanowisko Jagody dowiedział się podczas wczasów w Soczi, gdzie wypoczywał w ośrodku NKWD między innymi z Siergiejem Mironowem. Już w 1936 roku Frinowski został mianowany zastępcą nowego Komisarza Spraw Wewnętrznych Jeżowa.
Szef GUGB/pierwszy zastępca .
W październiku 1937 roku Frinowski zajął na miejsce Jakowa Agranowa stanowisko naczelnika Głównego Zarządu Bezpieczeństwa Państwowego NKWD, z rangi komkora został awansowany na komisarza bezpieczeństwa Państwowego 1 rangi tym samym został pierwszym zastępcą Ludowego Komisarza Spraw Wewnętrznych, Nikołaja Jeżowa. Na tym stanowisku Frinowski kierował śledztwem przeciwko marszałkowi Tuchaczewskiemu i czystką w Armii Czerwonej. W drugiej połowie 1938 roku Frinowski pojechał na Daleki Wschód z misją specjalną. Polegać ona miała na zmontowaniu prowokacji, której celem był marszałek Wasilij Blücher.
Ludowy komisarz marynarki wojennej Po przejęciu kontroli nad NKWD przez Berię Frinowski został oddelegowany z NKWD, został przeniesiony na jeszcze wyższe stanowisko, został mianowany ludowym komisarzem Radzieckiej Marynarki Wojennej i otrzymał awans o dwa stopnie, m.in.