Репрессии по национальному признаку не обошли и Красную Армию. 10 марта 1938 года Г.М. Маленков поручил Л.З. Мехлису подготовить списки армейских коммунистов — поляков, немцев, латышей, эстонцев, финнов, литовцев, болгар, греков, корейцев и представителей других национальностей, имевших государственные образования за пределами СССР. Указание было выполнено, и 24 июня того же года была издана директива наркома обороны, согласно которой из армии подлежали увольнению военнослужащие всех «национальностей, не входящих в состав Советского Союза». В первую очередь увольнялись все родившиеся или проживающие за границей, а также имеющие там родственников. Лица командно-начальствующего состава увольнялись из армии по приказам, имеющим особую нумерацию. После номера приказа за косой скобкой следовали буквы «оу» (например: Приказ № 115/оу), означавшие «особый учет». Уволенные с таким шифром (его называли «шифром Б.М. Фельдмана», по фамилии начальника управления по комначсоставу РККА) по прибытии на место жительства арестовывались. В числе уволенных с таким шифром были серб начдив Данило Сердич и поляк комбриг К.К. Рокоссовский.
По неполным сведениям (без данных по Киевскому и Забайкальскому округам, по Тихоокеанскому флоту и Дальневосточной флотилии), особыми отделами было выявлено 13 тысяч подлежащих увольнению «националов», 4 тысячи из которых уволены, 2 тысячи из числа уволенных арестованы. По директиве Наркомата обороны от 21 июня 1938 года из армии были уволены 863 политработника польской, немецкой, латышской, литовской, эстонской, китайской национальности. В июне — июле 1938 года производилась чистка армии по анкетным признакам (рождение, проживание или наличие родственников за границей). Из армии были уволены (и почти сразу в большей части арестованы) не только практически все военнослужащие и вольнонаемные «иностранных национальностей», но и немалое число представителей «национальностей Советского Союза». Согласно «Справке о числе уволенного начсостава РККА (без политсостава) в 1938 году по национальности», составленной в ноябре 1939 года в Управлении по командному и начальствующему составу РККА, всего за год было уволено 4138 командиров. Наибольшую часть уволенных составляли поляки (26,6 %), латыши (17,3 %), немцы (15 %) и эстонцы (7,5 %). Далее шли литовцы (3,7 %), греки (3,1 %), корейцы (2,9 %), финны (2,6 %), болгары (1,2 %). Среди уволенных были также венгры, чехи, румыны, шведы, китайцы — представители наций, «не входивших в состав народов СССР», и 710 человек (17,2 %) родившихся за пределами СССР русских, украинцев, белорусов, евреев и представителей других национальностей Союза ССР (Военно-исторический архив. 1998. № 3).
Аналогичным образом начиналась чистка другой силовой структуры. Н.И. Ежов, назначенный на пост наркома внутренних дел 26 сентября 1936 года, отмечал: «Придя в органы НКВД… начал свою работу с разгрома польских шпионов, которые пролезли во все отделы органов ЧК». В мае 1938 года ЦК партии дал указание об удалении из органов всех сотрудников, имеющих родственников за границей и происходивших из мелкобуржуазных семей. Массовая чистка органов госбезопасности была произведена после утверждения наркомом Л.П. Берия (25 ноября 1938 года). В 1939 году из органов госбезопасности были уволены 7372 человека (каждый пятый оперативный работник) и взято на оперативные должности 14,5 тысячи человек. Из руководящего состава НКВД (наркомы внутренних дел СССР и их заместители, начальники управлений и отделов центрального аппарата НКВД, наркомы внутренних дел союзных и автономных республик, начальники УНКВД краев и областей общей численностью 182 человека) исчезли поляки, латыши и немцы, значительно сократилось число евреев (с 21,3 % на начало сентября 1938 г. до 3,5 % к концу 1939 г.), места которых были замещены преимущественно русскими, украинцами, грузинами (Петров Н.В., Скоркин К.В. Кто руководил НКВД. М., 1999). Среди сотрудников центрального аппарата НКВД, насчитывавшего к началу 1940 года около 3,7 тысячи человек, русских было 3073 человека (84 %), украинцев — 221 (6 %), евреев 189 (5 %), белорусов — 46 (1,25 %), армян — 41 (1,1 %), грузин — 24 (0,7 %), а также представители татар, мордвы, чувашей, осетин и др.