Непростым было также становление советских органов военной контрразведки, всегда являвшихся важной составной частью системы обеспечения безопасности страны. Первоначально, с мая 1918 года, контрразведывательную работу в войсках вели органы Военного контроля (ВК), образованные Реввоенсоветом республики по аналогии с контрразведывательными отделениями царской армии и Временного правительства. Затем, помимо них, стали создаваться Чрезвычайные комиссии по борьбе с контрреволюцией на фронтах: первой из них стала ЧК на Чехословацком (Восточном) фронте, образованная 16 июля 1918 года. Ее председателем был назначен член Коллегии ВЧК М. Я. Лацис.
Для руководства фронтовыми ЧК при отделе ВЧК по борьбе с контрреволюцией 29 июля 1918 года был образован Военный подотдел. Особенно активно работа по укреплению отделов Военного контроля (ОВК) велась с сентября 1918 года, а 3 октября Реввоенсоветом было принято «Положение о военном контроле», согласно которому ВК вошел в качестве отдела в Регистрационное (разведывательное) управление Полевого штаба РККА.
Для ликвидации параллелизма в работе и с целью сосредоточения борьбы с контрреволюцией и шпионажем в армии в одном органе, а также с учетом фактов предательства со стороны отдельных военспецов, работавших в Военном контроле, 19 декабря 1918 года был образован Особый отдел ВЧК, штат которого первоначально составляли 11 сотрудников. В сентябре 1919 года для борьбы с контрреволюцией и саботажем в промышленности создается Экономический отдел ВЧК.
Помимо этого в феврале 1919 года был организован так называемый Секретный (впоследствии — Секретно-оперативный) отдел, задачей которого являлось наблюдение за членами и деятельностью антисоветских партий, политических групп и организаций, а также борьба с контрреволюционной угрозой со стороны этих сил.
Третья Всероссийская конференция чрезвычайных комиссий, состоявшаяся 1–3 июня 1919 года, приняла «Положение о секретно-политических отделах», задачей которых были «охрана революционного порядка и предупреждение и пресечение подготавливающихся или совершенных контрреволюционных явлений».
Поскольку вопрос о кадрах ВЧК всегда вызывал неизменный интерес, приведем на этот счет некоторые факты и цифры. Постановлением Совета труда и обороны республики от 17 сентября 1920 года «все лица, состоящие на службе в учреждениях, подведомственных ВЧК, как в центре, так и на местах, приравниваются к военнослужащим действующей Красной Армии, с возложением на них ответственности наравне с военнослужащими действующих полевых частей… и на них распространяются все законоположения, утвержденные ВЦИК в отношении воинской дисциплины».
После образования 30 декабря 1922 года Союза Советских Социалистических Республик ГПУ РСФСР, существовавшее с 6 февраля того же года, было преобразовано в Объединенное государственное политическое управление (ОГПУ) СССР. Пятнадцатого ноября 1923 года ЦИК СССР утвердил «Положение об ОГПУ и его органах на местах». Председатель ОГПУ входил в состав СНК с правом совещательного голоса.
Статус ОГПУ как государственного правоохранительного органа был зафиксирован и в главе IX Конституции СССР 1924 года (статьи 61–63).
При этом статья 63 устанавливала, что «надзор за законностью действий ОГПУ Союза ССР осуществляется прокурором Верховного Суда Союза ССР на основе специального постановления ЦИКа Союза ССР».
К концу 1921 года численность ВЧК, с учетом приданных ей частей особого назначения (ЧОН) и рабоче-крестьянской милиции, возросла до 130 тысяч человек, что значительно превосходило количество сотрудников Министерства внутренних дел Российской империи (84 тысячи человек). Это можно объяснить объективными историческими причинами: необходимостью отражения иностранной военной интервенции четырнадцати держав, а также ведением чрезвычайно жестокой Гражданской войны. После окончания Гражданской войны 6 февраля 1922 года была осуществлена реорганизация органов ВЧК, что позволило существенно сократить их численность. Так, на 1 августа 1922 года штат этот состоял из 49 487 сотрудников, а также 12 492 секретных сотрудников и 52 345 осведомителей. И если к 1 декабря того же года общая численность приданных ГПУ войск (отдельного пограничного корпуса, корпуса внутренних войск и конвойной стражи) составляла 116 тысяч человек, то к концу 20-х годов она сократилась до 68 941 человек рядового и младшего командного состава.