В июле — октябре 1937 года более тридцати слушателей Академии Генерального Штаба были отозваны с учебы и назначены на командные и штабные должности. Захаров вспоминал: «15 июля 1937 года меня срочно вызвали к Наркому обороны К. Ворошилову… Мне было предложено принять штаб Ленинградского военного округа… Через несколько дней я был принят командующим войсками Ленинградского военного округа П.Е. Дыбенко. Он встретил меня как старого знакомого, со свойственной этому легендарному человеку душевной теплотой. В тот же день вечером мы вместе с членом Военного совета М.П. Магером были на приеме у А.А. Жданова — секретаря ЦК и Ленинградского обкома партии, являвшегося по положению одновременно и членом Военного совета округа. В его кабинете состоялся интересный обмен мнениями по ряду важных вопросов боевой подготовки и воспитания воинов округа. Но работать в Ленинграде пришлось недолго…»
Из города на Неве Захарова перевели в Москву, на должность помощника начальника Генерального штаба по организационно-мобилизационным и материально-техническим вопросам, которую он занимал с мая 1938 по июль 1940 года. Затем он служил начальником штаба 12-й армии (июль — октябрь 1940), осуществлявшей освободительный поход в Бессарабию и Северную Буковину. «Штаб 12-й армии, — писал Захаров, — выполнив свою задачу, расположился в Черновицах. Вскоре был получен приказ о его расформировании».
С октября 1940 года он служил начальником штаба Одесского военного округа. В 1997 году журналист украинской газеты «Слово» Р. Денисенко в репортаже из музея округа писал: «А в соседнем зале висит фотография, уверен, мало известного одесситам генерал-майора Матвея Захарова. Он был начальником штаба ОдВО в самом начале Великой Отечественной войны. Именно благодаря ему округ оказался в основном подготовленным к встрече с врагом. В том, что война начнется, Захаров не сомневался. Нужно было действовать и одновременно удерживаться в рамках общеизвестной доктрины: "Не поддаваться на провокации”. Генерал по-одесски схитрил: под видом КШУ (командно-штабных учений) он отвел штаб на запасной командный пункт, отдал приказ проложить скрытно подземную телефонную связь и подготовил понтонные части для переправы войск. Примечательно, что практически все свои указания генерал Захаров отдавал устно.
Очевидно, поэтому он успел в обход кремлевских директив сделать так много полезного на своем посту». Письменного приказа на рассредоточение авиации по полевым аэродромам попросил только начальник ВВС Одесского военного округа. Как писал биограф маршала Захарова Б. Грязнов, «соединения округа организованно встретили противника, стойко отражая его атаки на суше и с воздуха. Генерал Ф.Г. Мичугин точно исполнил распоряжение начальника штаба М.В. Захарова, своевременно перевел все самолеты на запасные полевые аэродромы. Это позволило сохранить боеспособность воздушных сил. Когда утром 22 июня румынская и немецкая авиация бомбила основные аэродромы Одесского военного округа, Ф.Г. Мичугин поднял в воздух свои истребители, которые в течение дня сбили свыше 20 фашистских стервятников».
В ходе боевых действий штаб ОдВО развернулся в штаб 9-й армии, который в июне — июле возглавлял генерал Захаров. Армия вела сражения в приграничных районах СССР, отступая и вместе с тем нанося врагу большой урон. «Не случайно, — замечал Б. Грязнов, — медленнее всего гитлеровские войска продвигались именно в южном направлении».
В июле 1941 года М.В. Захаров возглавил штаб Главного командования Северо-Западного направления, во главе которого стоял К. Ворошилов, а членом Военного совета был А. Жданов. Штаб-квартира ГКСЗ находилась в Смольном. Проделанная командованием направления и его штабом большая работа, в том числе и обращение к войскам «всеми мерами борьбы приостановить дальнейшее вторжение врага на нашу территорию», дали свои результаты. В боях на лужском оборонительном рубеже продвижение врага было остановлено почти на месяц.
В августе 1941 года Захарова отозвали с фронта и назначили заместителем начальника только что созданного Главного управления тыла Красной армии, как специалиста в этой области. Но через несколько месяцев его вернули в войска и до конца войны он возглавлял штабы ряда фронтов. В январе 1942 — апреле 1943 года Матвей Васильевич Захаров был начальником штаба Калининского фронта. В январе 1942-го фронт в ходе Сычевско-Вяземской операции продвинулся более чем на 100 километров и перекрыл железную дорогу Вязьма — Смоленск. Однако замкнуть кольцо вокруг группировки немецко-фашистских войск Калининскому и Западному фронтам не удалось. В дальнейшем войска фронта вели бои местного значения. И только в августе оборона врага была прорвана и фронт продвинулся на 40–60 километров, освободив Зубцов и захватив северный берег Волги. Вместе с войсками Западного фронта калининцы в марте 1943-го перешли в наступление и, успешно выполнив поставленные задачи, освободили Ржев, Вязьму, Белый.