W 1936 ukończył Centralną Szkołę NKWD ZSRR. Od stycznia do lipca 1937 inspektor NKWD obwodu charkowskiego. W lipcu 1937 zwolniony ze służby i wydalony z partii za nieuzasadnione zamykanie spraw karnychros. за необоснованное прекращение уголовных дел i utrzymywanie kontaktów z bratem aresztowanym jako wróg ludu. Po pisemnych skargach został przywrócony do służby i skierowany do pracy w systemie obozów koncentracyjnych Gułagu jako zastępca naczelnika wydziału operacyjnego zarządu łagrów w Miedwieżjegorsku, a następnie Norylłagu (rejon Norylska). W listopadzie 1939 kpt. b.p. Miedwiediew został ponownie zwolniony ze służby, oficjalnie z przyczyn zdrowotnych.
Po ataku III Rzeszy na ZSRR w czerwcu 1941 r. przywrócony do czynnej służby w NKWD i skierowany pod komendę mjr b.p. Pawła Sudopłatowa. Przeszedł przeszkolenie w ramach Samodzielnej Zmotoryzowanej Strzeleckiej Brygady Specjalnego Przeznaczenia (OMSBON NKWD). Na początku września stanął na czele grupy dywersyjnej OMSBON Mitiaros. разведывательно-диверсионная резидентура № 4/70 Особой группы при наркоме НКВД СССР, którą przerzucono na znany Miedwiediewowi teren okolic Briańska, gdzie w lasach zorganizował oddział partyzancki na jej podstawie. Była to pierwsza tego typu grupa dywersyjna przerzucona przez linię frontu. Od września 1941 r. do stycznia 1942 r.