Большевики не могли выиграть Гражданскую войну без сравнительно хорошо дисциплинированных военных сил. Однако сложности создания такой армии были огромными. Страна была опустошена, люди устали от борьбы, а укоренившиеся привычки и идеология большевиков мешали им решить свои военные задачи. Они всегда считали армии и милитаризм одними из наиболее опасных врагов революции. На протяжении 1917 года они использовали любую возможность внести вклад в разобщённость армии, поощряя желание крестьян вернуться домой и отстаивая такие утопические и подрывные идеи, как выборы командного состава. Они слишком хорошо преуспели. Когда-то могущественная армия, крупнейшая из тех, что когда-либо видел мир, прекратила существование как военная сила. После своей победы большевики смогли рассчитывать только на мизерные отряды партизанского типа, которые были полезны против почти не существующей контрреволюции, но которые были беспомощны при столкновении с регулярными военными силами.
Троцкий быстро расстался с иллюзиями. Он стал комиссаром по военным делам в марте 1918 года и немедленно приступил к созданию регулярной армии. Он основывал свою политику на убеждении, что Красной армии, прежде всего, требуются организация и дисциплина. Он намеревался истребить партизанщину (партизанские приёмы ведения войны), метод борьбы, к которому он чувствовал личную ненависть.
Когда Чехословацкий легион восстал против большевиков в мае 1918 года, быстро стало ясно, что Красная армия не может привлечь достаточного количества добровольцев. Во всей огромной стране было не более 200.000 солдат, сражавшихся в неорганизованных, партизанского типа отрядах, которые имели исключительно низкую военную ценность. Через несколько дней после восстания чехов большевики объявили мобилизацию. Набор в армию сначала распространялся только на рабочих, затем на бедных крестьян и наконец на всех крестьян, за исключением размытой категории кулаков. Кулакам, наряду со своим городским эквивалентом, буржуазией, вместо этого приходилось служить в трудовых батальонах. Армия быстро росла. К середине сентября в строю у красных было 452.000 человек, а к концу Гражданской войны — пять миллионов. Даже несмотря на то, что в Красной армии было непропорционально много, по сравнению с их процентом в населении страны, рабочих, и они несли большие потери в живой силе, подавляющее большинство солдат было из крестьянства. Сначала в армию призывали только тех крестьян, у кого был боевой опыт в Мировой войне, но вскорости пришлось обратиться к тем, кто в то время был слишком молод, чтобы воевать. Поскольку в условиях Гражданской войны они получали небольшую подготовку, военная ценность молодых крестьян была незначительной.
Даже более сложной задачей, чем призыв крестьян, было обеспечение армии командным составом. Примечательно, как быстро Троцкий обнаружил единственно возможное решение и затем неуклонно его придерживался, несмотря на сложности и противостояние, с которыми он столкнулся. Он без колебаний отменил принцип выборов офицеров и решил воспользоваться услугами квалифицированных людей — тех, кто уже служил царю и Временному правительству. В ноябре 1918 года в Красной армии служили примерно 22.315 бывших царских офицеров. К концу Гражданской войны эта цифра составляла почти 50.000. Кроме того, большевики получили огромное преимущество от службы более чем 200.000 человек, которые участвовали в Первой мировой войне как сержантский состав.
Пролетарское государство предпринимало громадные усилия по обучению «красных командиров»; бывший сержантский состав и даже рядовые второпях проходили экспресс-курсы и отправлялись на фронт командовать батальонами. Однако их никогда не хватало. В конце 1918 года две трети офицеров получили подготовку в старой армии, и даже в конце Гражданской войны их процент не упал ниже 5018. Даже эти цифры преуменьшают значимость вклада хорошо обученных офицеров, поскольку более высокие должности, где принимались жизненно важные стратегические решения, были почти целиком заполнены этими людьми. Без их практического опыта Красная армия никогда бы не смогла разбить врага.
Очень немногие из офицеров были добровольцами; большинство из них заставили служить под угрозой наказания. В таких условиях большевики имели основания бояться предательства. Действительно, многие из офицеров при первой возможности переходили на сторону врага. Троцкий пытался снизить опасность, предоставляя хорошие условия работы тем, кто служил верой и правдой, беспощадно наказывая виновных и введя новую должность политического комиссара. В момент, когда в российской армии впервые появились комиссары, когда у власти стояло Временное правительство, они закреплялись только за крупными военными подразделениями, такими как фронт и армии. После ноября 1917 года комиссары получили новые обязанности и направлялись в каждую воинскую часть вплоть до уровня роты. У них было две основные функции: курировать работу военных специалистов и организовывать пропаганду среди солдат. На первых стадиях Гражданской войны политические комиссары подписывали оперативные распоряжения командования и таким образом создавали систему двойного командования. В начале 1919 года Троцкий упразднил эту систему и освободил комиссаров от непосредственной ответственности за чисто стратегические решения. Новая система вела к дублированию и недоразумениям. Как комиссар должен был предотвращать предательство, если он не мог вмешиваться в военные решения? Однако эти люди, в большинстве своём простые рабочие и крестьяне, сыграли решающую роль в победе в Гражданской войне. Их неустанная агитация против «белогвардейских монархистов» и «контрреволюционеров» действительно поднимала моральный дух войск.
Военная политика Троцкого и прежде всего привлечение им на службу царских офицеров привели к жестокому расколу большевистской правящей верхушки. Некоторые возражали против воссоздания организованной и дисциплинированной армии по либертарианским мотивам. Другие считали унизительным, что те же самые люди, против которых боролась революция, сейчас снова оказались на влиятельных и ответственных постах. Ленин поддерживал Троцкого, так что комиссар по военным делам добился своего, однако сам Ленин оставался в стороне от повседневной борьбы. Наём царских офицеров был политикой Троцкого, и именно ему пришлось нести бремя ответственности. И.В. Сталин, который летом 1918 года стал политическим комиссаром Южного фронта, возможно, из-за неприязни к комиссару по военным делам, защищал тех, кто сопротивлялся дисциплине и осуждал наём военных специалистов. Поскольку его противники были сильны, Троцкому не удалось провести свои реформы повсеместно в армии. Некоторые подразделения, преимущественно в удалённых регионах, оставались поражёнными духом партизанщины, и их боеспособность оставалась исключительно низкой. Расхождения во мнениях между Троцким и его противниками проявлялись в большом количестве вопросов, как организационных, так и стратегических, и распри в рядах большевиков значительно ослабляли Красную армию.
Помимо нехватки квалифицированных и надёжных офицеров, Красная армия страдала от нехватки снабжения и вооружения. В первый период Гражданской войны ситуация не была неблагополучной. Армия была ещё относительно малочисленной, а склады прекратившей своё существование императорской армии были богатыми. Но армия росла, и поставки постепенно оскудевали. Напротив, белые начали получать значительную помощь из-за границы. Летом 1919 года, в период решающих сражений, ситуация с поставками превратилась в критическую.
В этих условиях выживание режима зависит от его способности организовать экономическую жизнь в стране достаточно хорошо, чтобы обеспечить армию необходимым. Большевики занимали главные центры российской военной промышленности: Тулу, Москву, Петроград и Царицын, но районы производства сырьевых материалов на Украине, и в особенности в Донецком бассейне, были заняты противником. Для обеспечения армии требовалось огромное организаторское мастерство. Большевики, сконцентрировав свои силы на этой жизненно важной задаче, преуспели. С апреля по декабрь 1919 года военные заводы производили ежемесячно в среднем 28.7 млн патронов. Тула, возможно, самый важный центр страны, увеличила ежемесячное производство с 16.000 ружей в апреле до 27.000 в декабре, а производство пулемётов за этот же период выросло с 325 до 4562 штук. Несмотря на эти огромные усилия, белые с помощью союзников обычно были лучше вооружены, чем красные в 1919 году.
Красная армия также страдала от недостаточной профессиональной организации, как минимум в течение первых месяцев своего существования. В сентябре 1918 года большевики предприняли важный шаг к исправлению этой ситуации. Троцкий возглавил новосозданный Высший военный совет, который нёс ответственность за ведение боевых действий. В то же время И.И. Вацетис, бывший полковник императорской армии, стал главнокомандующим всеми вооружёнными силами республики. По примеру царской армии красные войска были организованы в «армии» и «фронты». Бывший императорский офицер генерал П.П. Сытин принял командование Южным фронтом, который включал в себя 8-ю, 9-ю, 10-ю, 11-ю и 12-ю армии. 8-я, 9-я и 10-я армии сражались на Дону против атамана Краснова, а 11-я и 12-я в это время на Северном Кавказе противостояли силам Деникина. В силу проблем коммуникации и логистики подчинение 11-й и 12-й армий командованию Южного фронта было только теоретическим. В действительности эти две армии формировали отдельный фронт, а действия красных против Краснова и Деникина были плохо скоординированными.
Без реформ Троцкого Красная армия не смогла бы пережить трудный 1919 год. В январе кольцо вокруг удерживаемой Советами России почти полностью сомкнулось. Войска союзников находились в Мурманске и Архангельске; финская армия Маннергейма была резко враждебна по отношению к большевикам; новосформировавшиеся балтийские государства становились базами для интервентов и антибольшевиков; Польша Пилсудского только и ждала благоприятного момента атаковать и связывала большое количество войск красных; французы высадились в Одессе и в Крыму и угрожали перейти границы Украины, а в Сибири собирал войска адмирал Колчак. Юг был колыбелью антибольшевистского движения. Здесь крупнейшей военной силой была Донская казачья армия атамана Краснова. Добровольческая армия была всё ещё вовлечена в действия на Северном Кавказе, но у большевиков была причина бояться её потенциального роста и мощи.
Против всех своих врагов большевики могли выставить только 380.000 человек. Большая часть Красной армии находилась на юге: 47.000 на Украине, 117.000 на Дону и 35.000 на Кавказе. Некоторые сражались с Колчаком, а остальные были стянуты на запад. Стратегические планы Троцкого предусматривали быструю оккупацию Украины, поскольку он боялся, что украинские националисты с помощью французов могут стать огромной опасностью. Ленин, с другой стороны, сначала хотел уничтожить Донскую армию, чтобы предотвратить коалицию восточных и южных контрреволюционеров. Итоговый компромисс никого не удовлетворил. Главное командование отправило подкрепление на Донской фронт, но недостаточно, чтобы одержать решающую победу. На Украине Красная армия достигла серьёзных успехов и овладела всей территорией, но на востоке и на юге белые собирали силы и представляли собой все бо́льшую опасность.