Ольдерроге настаивал на возвращении к своему плану и соответствующей перегруппировке войск. Как вспоминал Тухачевский, «произошла крепкая телеграфная перепалка, но Ольдерроге категорически настоял на перегруппировке. Белые учли эту ошибку. Уже на подступах к Петропавловску они перешли в контрнаступление, сковали части 5-й армии с фронта, а на правый фланг и тыл двинули с юга две пехотные дивизии», вновь сформированный Сибирский казачий конный корпус сибирского атамана генерала П. П. Иванова-Ринова и конную группу генерала Доможирова. Корпус сибирских казаков разбил одну из бригад 26-й стрелковой дивизии, опрокинул войска Тухачевского и погнал их назад, к Тоболу. «Никому не известный, в лучшем случае бездарный» Ольдерроге спас легендарных «пятоармейцев» от разгрома, подкрепив армию Тухачевского дивизией из фронтового резерва и бросив против левого фланга ударной группы белых соединения 3-й армии, также форсировавшей Тобол. Благодаря этому 5-я армия отошла за реку без больших потерь и удержала плацдарм на правом берегу Тобола. 14 октября, пополненная за счет мобилизации рабочих Челябинска и других уральских городов и вновь сформированной кавалерийской дивизии, 5-я армия перешла в наступление и 29 октября овладела Петропавловском. Противник в беспорядке отступал к Омску. Здесь опять возник конфликт между Ольдерроге и Тухачевским. Командарм-5 хотел бросить кавалерийскую дивизию на перехват путей отхода белых от Омска, но командующий фронтом настоял, чтобы она была направлена для обеспечения правого фланга армии со стороны Кокчетава. Трудно сказать, кто же из них в действительности был прав. С одной стороны, фланговая угроза оказалась значительно преувеличенной: казаки отступили от Кокчетава на Акмолинск. С другой стороны, как признавал сам Тухачевский, в ходе операции действия кавалерийской дивизии «не носили характера достаточной решительности», вследствие чего она «не достигла всех тех результатов, которых… могла достигнуть». Так что вряд ли бы этой дивизии удалось предотвратить отход из Омска основных колчаковских сил. Скорее ей грозило бы поражение. Во всяком случае, на исход операции отсутствие кавдивизии в тылу омской группировки не оказало существенного влияния. 14 ноября 1919 года столица верховного правителя России пала под ударами 3-й и 5-й советских армий. На пути от Петропавловска до Омска было взято 45 тыс. пленных, в самом Омске было захвачено еще 16 тысяч раненых и больных тифом колчаковских солдат и офицеров.
За победу над Колчаком 5-я армия была награждена орденом Красного Знамени и Почетным Красным Знаменем ВЦИК. А ее командующий 17 декабря 1919 года удостоился высшей в то время награды — Почетного Революционного оружия, представлявшего собой позолоченную шашку с вмонтированным в ножны орденом Красного Знамени. Такое отличие было пожаловано Тухачевскому «за личную храбрость, широкую инициативу, энергию, распорядительность и знание дела, проявленные им при победоносном шествии доблестной Красной Армии на восток, завершившемся взятием города Омска».
В только что освобожденном от колчаковцев Омске Тухачевский после долгой разлуки встретил своего друга Кулябко, назначенного членом Сибревкома. Что-то символическое было в этой встрече. С Кулябко Тухачевский расстался, когда уехал на Восточный фронт, именно ему сначала сообщил о своем первом успехе на Восточном фронте, и вновь встретился с другом в день разгрома Колчака и фактической ликвидации Восточного фронта. Портрет командарма в тот знаменательный день запечатлел в своих воспоминаниях боец 5-й армии Н. В. Краснопольский: «Это был красивый молодой человек в ладном барнаульском полушубке, валенках и белой сибирской заячьей шапке с длиннющими ушами, которыми при нужде можно было закрыть и шею». Несколько экзотическое для военачальника, но со вкусом подобранное одеяние диктовалось суровым омским морозом.
Теперь организованное сопротивление основных сил белых на востоке почти прекратилось. С ними должны были покончить сибирские партизаны и морозы. Красные дивизии еще с конца лета ускоренно перебрасывались с востока на юг, против Деникина. После падения Омска был отозван в Москву и Тухачевский. На бывшую его 5-ю армию легла основная тяжесть борьбы с войсками верховного правителя, и за Михаилом Николаевичем закрепилась слава победителя Колчака. У руководителей государства он завоевал солидный авторитет. На совещании политработников Красной Армии в декабре 1919 года Троцкий назвал Тухачевского «одним из лучших командармов», особо отметив его «стратегический талант». 18 декабря Тухачевского принял Ленин, попросивший его составить доклад об опыте использования военных специалистов в 5-й армии. Командарм не заставил себя ждать и уже на следующий день направил текст доклада заместителю председателя Реввоенсовета Э. М. Склянскому. Тухачевский особо подчеркивал роль тех бывших царских офицеров, что уже успели стать членами партии. Он довольно низко оценивал дореволюционный офицерский корпус в целом: «У нас принято считать, что генералы и офицеры старой армии являются в полном смысле слова не только специалистами, но и знатоками военного дела… На самом деле русский офицерский корпус старой армии никогда не обладал ни тем, ни другим качеством. В своей большей части он состоял из лиц, получивших ограниченное военное образование, совершенно забитых и лишенных всякой инициативы». Указав на реформу военной школы после русско-японской войны, Тухачевский оговорился, что ее результаты стали сказываться лишь к 1908–1910 годам. Поэтому «хорошо подготовленный командный состав, знакомый основательно с современной военной наукой и проникнутый духом смелого ведения войны, имеется лишь среди молодого офицерства… Значительная его часть, как наиболее активная, погибла в империалистической войне. Большая часть из оставшихся в живых офицеров, наиболее активная часть, дезертировала после демобилизации и развала царской армии к Каледину, единственному в то время очагу контрреволюции. Этим и объясняется обилие у Деникина хороших начальников. Среди старого офицерства способные начальники являются исключением».
В докладе отразился личный опыт командарма, неоднократно конфликтовавшего и с коммунистами-комиссарами, и с вышестоящими беспартийными начальниками из штаб-офицеров и генералов. Здесь Тухачевский противопоставляет молодых офицеров в небольших чинах их более старшим товарищам, генералам и штаб-офицерам — в чине полковников и подполковников. 26-летний командарм верил, что «из среды… скороспелого офицерства», прошедшего ускоренный курс обучения во время войны, «мы имеем больше хороших командиров, чем из среды старых офицеров». Поскольку многие из молодых офицеров занимали в то время «очень ответственные посты», Тухачевский делал смелый и радикальный вывод о том, что «возможность командования вовсе не сопряжена с такими трудностями, чтобы они не были достижимы для наших партийных товарищей». Он доказывал: «Только в службе генерального штаба, в штабной работе старое офицерство имеет преимущества перед новичками». Автор доклада ратовал за «свой, коммунистический командный состав, который будет не только энергичным и самодеятельным, не только позволяющим Коммунистической партии надежно проникнуть в массы Красной Армии и обеспечить ее за собой», но и сделает шаг вперед «в отношении осмысленного руководства армией на войне». Тухачевский убеждал Склянского, Троцкого и Ленина в необходимости установления единоначалия, путем выдвижения на командные посты военкомов и командиров-коммунистов из числа младших офицеров и унтер-офицеров: «Среди военкомов и младшего комсостава есть много достойных быть командирами на ответственных постах. Надо только дать широкий простор для продвижения и широко назначать военкомов на командные должности, давая некоторым из них краткую теоретическую подготовку. Во всяком случае, все военкомы из бывших офицеров или унтер-офицеров должны быть сразу обращены в командный состав. Нужно только бросить лозунг о переходе к коммунистическому командному составу (в главной массе), и этот командный состав появится, так как он уже имеется налицо в скрытом виде… В 5-й армии уже давно выдвинут этот лозунг, и командный состав в ней весь коммунистический, а боевая действительность доказывает и превосходство его над генералами и старыми офицерами».
