В начале января он вступил в новую должность, но уже 24 января 1919 года принял командование 8-й армией. Через полтора месяца Тухачевского вернули на Восточный фронт, поставив его во главе 5-й армии. Она отступала под натиском белой Западной армии генерала М.В. Ханжина.
Тухачевский смог восстановить боеспособность 5-й армии, одновременно участвуя в подготовке контрнаступления Южной группы армий Восточного фронта, которой командовал М.В. Фрунзе. Оно началось 28 апреля, и уже 5 мая войска Тухачевского заняли Бугуруслан, продолжая наступать на Бугульму. Тем временем ситуация на фронте изменилась: сосед 5-й армии слева – 2-я армия – под сильным давлением белых стал отходить к реке Вятка. Одновременно от Бугульмы стал наступать 1-й Волжский корпус генерала В.О. Каппеля.
В ходе последующих боев командарм 5-й армии получил от нового командующего Восточным фронтом А.А. Самойло, сменившего на этом посту С.С. Каменева, несколько приказов о смене направления ударов. В итоге действия армии оказались парализованными. Возмущенный Тухачевский направил в штаб фронта незашифрованную телеграмму, «дискредитирующую высшую власть в боевое время». Конфликт грозил командарму снятием с должности. Но за него заступился военспец в лице Самойло, и дело уладилось.
В начале июня войска 5-й армии форсировали реку Белую и начали продвижение к Уральскому хребту. Тухачевскому удалось скрытно провести перегруппировку своих войск. Его противник в лице командующего колчаковской Западной армией генерала Ханжина принял отвлекающий удар красных за главный. Поэтому он обратил свое внимание на район Белорецка и Верхнеуральска.
Тухачевский же пошел в наступление силами 26-й и 27-й стрелковых дивизий севернее, которые вскоре оказались в тылах у главных сил Ханжина. Противник начал отход. 13 июля красные взяли город Златоуст, разгромив здесь резервный Уфимский корпус белых. Затем быстрым ударом был занят Челябинск, где войска 5-й армии выдержали ряд сильных фланговых контрударов. Они обороняли Челябинск больше недели, пока атакующий пыл колчаковцев не иссяк.
Эти бои совпали с годовым юбилеем образования 5-й армии. Председатель Реввоенсовета Республики Л.Д. Троцкий издал поздравительный приказ, адресованный личному составу армии. Она награждалась Почетным знаменем Московского Совета и орденом Красного Знамени.
Реввоенсовет Республики 4 августа принял постановление занести имя 5-й армии на Почетную золотую доску в зале Красного Знамени РВСР. Через два дня был издан приказ о награждении ее командующего М.Н. Тухачевского орденом Красного Знамени. В приказе говорилось:
«Доблестные войска 5 армии под искусным водительством командарма т. Тухачевского после упорнейших боев, разбив живую силу врага, перешли через Урал. Бугуруслан, Бугульма, Бирск и Златоуст пали под нашими ударами благодаря смелым, полным риска, широким маневрам армии, задуманным т. Тухачевским. 24 июля 1919 г. геройскими частями 3 бригады 27 дивизии взят Челябинск.
Огромный успех, достигнутый армией, является результатом, главным образом, талантливо созданного т. Тухачевским плана операции, который твердо проведен им в жизнь».
Наступление на армии Колчака в Зауралье продолжалось. 5-я армия 20 августа форсировала реку Тобол и вышла на дальние подступы к городу Петропавловску. Однако соперник Тухачевского генерал Сахаров со своими сибиряками, подтянув резервы, сильным контрударом отбросил войска 5-й армии обратно за Тобол, где те перешли к обороне. Потом напишут, что Тухачевский «решил отойти за Тобол» с разрешения нового командующего Восточного фронта В.А. Ольдерогге, тоже из дворян, генерал-майора старой армии, выпускника Академии Генерального штаба.
5-й армии на Тоболе противостояли Степная, Уральская, Волжская и Уфимская группы. Колчаковцы имели двойное превосходство в кавалерии (казачьей коннице), но в полтора раза уступали красным по количеству штыков. Этим преимуществом и задумал воспользоваться М.Н. Тухачевский, планируя новую наступательную операцию.
В прифронтовой полосе была объявлена мобилизация, и дивизии армии, понесшие большие потери в предыдущих боях, восстановили свою силу. Была сформирована кавалерийская дивизия (13-я) во главе с В.Д. Соколовским, будущим Маршалом Советского Союза и начальником Генерального штаба. На усиление армии прибыла 54-я стрелковая дивизия бывшего штабс-капитана Ф.К. Калнина (Калниньша).
Была создана армейская ударная группа, нацеленная на стык Уральской и Степной групп белых. Затем должен был последовать разгром окруженной Уральской группы. Наступление велось по линии Транссибирской железнодорожной магистрали. В начале операции предстояло форсировать Тобол: в полосе 160 километров армейские инженеры навели 24 переправы. Армия получила возможность перехода через реку одновременно на широком фронте.