Однако эта структура долго не просуществовала. Во время неразберихи, царившей на брест-литовских переговорах, Германия возобновила на некоторое время своё наступление. Это послужило жестоким напоминанием о беспомощности и донкихотстве новой русской армии. Троцкий решил её ликвидировать и построить заново на более традиционных принципах. Он учредил Верховный Военный Совет под руководством царского генерала Бонч-Бруевича для выполнения задачи создания новой армии. По всей территории, контролируемой красными, была раскинута сеть военных комиссариатов для набора рекрутов, сначала на добровольных началах, а затем, после чешского мятежа, в качестве принудительной воинской повинности. Подразделения Красной гвардии и милиции большей частью были расформированы как ненадёжные, из каждого из них было взято лишь по несколько членов партии для создания ядра вновь сформированных и традиционно устроенных полков. Но кому же командовать новыми подразделениями? У партии не было под рукой достаточного количества людей с необходимой военной подготовкой и опытом для командования войсками в условиях современных военных действий. При поддержке Ленина Троцкий обратился к офицерам старой царской армии, по крайней мере, к тем, кто не ушёл служить белым. Их знаки отличия и звания не были восстановлены, но в остальных отношениях им дали дисциплинарные полномочия, к которым они привыкли, вплоть до права карать смертью за неподчинение. Никаких глупостей типа «солдатских комитетов» больше не существовало: они были попросту отменены, а на смену им пришли «политические комиссары». Они назначались с одобрения партии и должны были находиться рядом с офицерами (некоторые из них, по крайней мере сначала, неохотно стали служить красным) для обеспечения их лояльности, передачи политических указаний и поднятия уровня политического сознания среди призванных на военную службу. Комиссар явным образом не был подчинён офицеру, а был ему равен, обладая при этом правом казнить офицера, если тот совершит предательство по отношению к Красной Армии.
Методы Троцкого вызвали волну критики как внутри партии, так и вне её. Во ВЦИКе меньшевик Дан воскликнул: «Так появляются Наполеоны!», в то время как внутри партии так называемая «военная оппозиция» призывала вернуться в принципу милиции и сместить старорежимных офицеров. Как бы то ни было, Троцкий создал эффективную военную организацию под предельным контролем партии. Учитывая, в какой спешке она создавалась и как велики были стоящие перед ней задачи, Красная Армия воевала исключительно хорошо, и можно признать, что моральный дух в её рядах был выше, чем в каком-либо ином слое населения России. Конечно же, войска получали лучшее питание, чем практически кто-либо ещё в то время, и служба в Красной Армии была замечательным способом продвижения в новом обществе. Сотни тысяч рабочих и крестьян в Красной Армии вступали в партию, и некоторые из них по этой причине заняли позднее высокие и ответственные посты в новом обществе. Троцкий действительно делал всё от него зависящее, чтобы солдаты Красной Армии получали специальную подготовку и продвигались на командные посты по возможности быстрее. К концу гражданской войны эти новые выдвиженцы составляли две трети офицерского корпуса; некоторым суждено было прославиться во время второй мировой войны. Всё это сильно сказалось на социальной структуре партии.
Другим основным инструментом революционного режима стала ЧК. Как мы уже знаем, она была учреждена таким образом, что не подлежала контролю ни со стороны партии, ни со стороны советов. Она возникла вне даже тех придуманных на скорую руку законодательных норм, которые новый режим для себя установил. В самом деле, можно сказать, что ЧК воплощала ленинскую противоречивость в вопросах демократии и авторитаризма.