Под натиском Красной армии интервенты уже в апреле 1919-го покинули город. Пока бандиты Япончика грабили банки и магазины, подпольщики Котовского взяли Одессу под свой контроль. После восстановления Советской власти ревком поручил «испытанному и боевому товарищу Котовскому» (который ещё не являлся членом партии) собрать добровольцев для освобождения Бессарабии, а потом — для похода на помощь революционной Венгрии.
Этот план оказался сорван мятежом атамана Николая Григорьева, а потом — наступлением белых. В июле Котовского назначили командиром 2-й пехотной бригады 45-й стрелковой дивизии — это была его первая должность в Красной армии. Комиссаром бригады стал тюремный товарищ атамана Исай Шмидт — будущий историк и ректор Одесского университета. Должность фельдшера заняла молодая вдова Ольга Шакина, на которую скоро «положил глаз» сам комбриг. В конце войны они сыграли свадьбу, родились дети — дочь Елена и сын Григорий, известный востоковед, очень похожий на отца.
Котовцам предстояло три года непрерывных походов и боёв. В июне они сражались с петлюровцами, рвавшимися к Одессе с севера. Потом с востока нахлынула Добровольческая армия, 25 августа при поддержке британской эскадры занявшая Одессу. Пройдя по тылам противника, бригада Котовского вышла на советскую территорию и была переброшена к Петрограду, которому угрожали войска Николая Юденича. Этот поход на голодный и холодный север дорого обошёлся бойцам-южанам — многие из них, включая комбрига, тяжело заболели. После выздоровления Котовский командовал кавалерийской бригадой в боях с деникинцами, а в феврале снова занял Одессу и отбросил последних белогвардейцев к румынской границе. Чуть не взятый им в плен Василий Шульгин отзывался о комбриге с похвалой:
«Во всей округе рассказывали, что он собственноручно застрелил двух красноармейцев, которые ограбили наших больных офицеров».
В отличие от многих красных командиров, Котовский строго запрещал грабить, а тем более расстреливать пленных и вообще соблюдал строгую дисциплину.
Покончив с белыми, 45-я дивизия вскоре столкнулась с новым опасным противником — поляками, которые в апреле 1920 года начали наступление на Украине. К ним тут же примкнули петлюровские отряды и часть украинских частей Красной армии. Под натиском врага красные отступили, оставив Киев, хотя уже в июне Конармия взломала фронт поляков и погнала их на запад. Котовский тоже повёл свою бригаду в наступление, но в июле был сильно контужен и отправлен лечиться в Одессу. Жена осталась на фронте, и он чуть ли не каждый день писал ей нежные письма:
«Милая, дорогая, желанная Лелечка! Каждый раз, когда приходит летучка „оттуда“, где ты, моя родная, ненаглядная, душа моя переживает какой-то удивительно сложный и сильный по остроте своего переживания момент. Каждый раз хочу послать тебе на бумаге то, что у меня на душе, — мое чувство… Эх, да разве вместит весь мир мою любовь?!»
В августе Котовский выздоровел и собирался вернуться в бригаду, однако она сама двинулась ему навстречу, разбитая поляками вместе с остальными советскими войсками. Котовцы понесли тяжёлые потери, погиб и их командир Михаил Ульрих, с начала войны воевавший рядом с Котовским. Даже в суматохе отступления они не запятнали себя грабежами и погромами, как другие красные части. Роман Гуль, автор очерка об атамане, писал:
«Котовский любил кавбригаду, как огородник любит свой огород, как охотник любит своих борзых и гончих. Самолично подбирал командиров, сам среди пленных разыскивал отменных рубак… В кавбригаде вместе с прошедшими всю войну красными партизанами смешались белые казаки-деникинцы, шкуринцы, военнопленные мадьяры, немцы, беглые поляки и чехи. Подбор вышел хорош».
В конце 1920 года бригада отбросила петлюровские части к границе, после чего Котовского назначили командиром 17-й кавалерийской дивизии. Война для него не кончилась: до конца 1922 года он гонял по Украине всевозможных атаманов, побывал и на Тамбовщине, где подавлял Антоновское восстание. В октябре того же года он стал командиром 2-го кавалерийского корпуса, расквартированного в Умани недалеко от Киева. Никто не думал, что это венец его карьеры: есть мнение, что нарком Михаил Фрунзе хотел сделать Котовского своим заместителем. По другой версии, его собирались всё-таки отправить на отвоевание родной Бессарабии. Базой для этого должна была стать созданная в 1924 году в Тирасполе Молдавская АССР. Пока же бывший атаман с удовольствием готовил солдат. Он требовал, чтобы все бойцы занимались физкультурой, по утрам умывались холодной водой, зимой растирали себя снегом. Приказал закупить для корпуса спортивные снаряды, а также духовые инструменты — музыку он любил не меньше спорта.