Учитывая это, советское правительство и партия 3 декабря 1920 года назначили Фрунзе командующим всеми вооруженными силами на Украине и поручили ему в кратчайший срок искоренить бандитизм и прежде всего махновщину.
Фрунзе немедленно приступил к выполнению очередного боевого поручения, используя свой богатый опыт борьбы с басмачеством в Туркестане. Еще до нового назначения он повел решительную борьбу с отрядами Махно, которые еще недавно, в качестве «повстанческой армии», находились в подчинении Фрунзе — командующего Южным фронтом и принимали некоторое участие в борьбе за освобождение Крыма от врангелевцев. Но уже в то время «повстанческая армия» Махно окончательно разложилась, подпав под кулацко-анархистское влияние, и преступно нарушала военную дисциплину. До Фрунзе стали доходить сведения о бандитских проступках махновцев, об их грабежах и убийствах, о кровавых столкновениях с красноармейскими частями.
23 ноября 1920 года Фрунзе издал приказ о расформировании «повстанческой армии». В ответ на это Махно открыто выступил против советской власти и встал на путь безудержного бандитизма. Некоторое время его шайки безнаказанно бесчинствовали в Гуляй-Польском районе, Запорожской области. Но затем они были здесь окружены. Лишь ценой больших потерь им удалось в конце декабря вырваться из кольца советских войск и скрыться в просторах правобережной Украины.
Там Махно стал применять тактику неожиданных налетов, внезапно появляясь в каком-нибудь районе и так же внезапно исчезая. В этом ему помогала кулацкая часть украинского крестьянства. Вследствие этого борьба с махновщиной весьма осложнилась. Требовалось изыскать и применить особые средства и приемы борьбы.
Фрунзе нашел эти средства. Среди украинского селянства провели широкую разъяснительную кампанию о сущности махновщины, об ее враждебности интересам трудового народа, о необходимости борьбы с нею. Наряду с этим, по приказу Фрунзе, сформировали «летучий корпус», отряды которого должны были не только преследовать махновцев, но и перерезать им пути их отступления, окружать и беспощадно истреблять. Такая тактика борьбы, удачно примененная Фрунзе еще в Туркестане, полностью оправдала себя и здесь.
Скоро преследуемые по пятам, махновские банды заметались под ударами отрядов «летучего корпуса». Теснимые отовсюду, они с трудом пробирались из одного района в другой, не встречая прежней поддержки у местного населения. С каждым месяцем банды таяли, бывшая «армия» превратилась в жалкий сброд обреченных головорезов. Чувствуя неизбежность гибели, Махно с кучкой своих наиболее отпетых сторонников тайком пробрался к берегам Днестра и здесь в августе 1921 года переправился в Бессарабию, где и нашел свой последний приют под защитой румынского правительства.
Во время борьбы с махновщиной Фрунзе не только руководил, но и принимал сам непосредственное участие в боевых операциях, показывая пример личного героизма.
За личную храбрость и мужество, проявленные в период борьбы с бандитизмом, Михаил Васильевич был награжден вторым орденом Красного Знамени.
На Украине Фрунзе принимал активное участие в государственной жизни страны.
В ноябре 1921 года по поручению украинского правительства он выехал в Турцию в качестве чрезвычайного посла для заключения дружественного договора с Турцией, сбросившей с себя вековое иго султана и боровшейся в то время с империалистами-захватчиками. Задание было выполнено с большим успехом. За короткое время Фрунзе сумел расположить к себе представителей турецкого правительства и завоевал симпатии народных масс молодой Турецкой республики.
Возвратившись из Турции, Фрунзе в качестве члена украинского правительства (а одно время он исполнял обязанности предсовнаркома УССР) много сделал для культурно-хозяйственного развития республики. Руководствуясь ленинско-сталинской национальной политикой, он всячески содействовал процветанию украинского народа, всемерно укреплял вековую дружбу братских народов — украинского и русского. Под руководством товарища Сталина Фрунзе участвовал в разработке проекта первой Конституции Советского Союза.
