По итогам Советско-финляндской войны в аппарате Наркома обороны произошли серьезные изменения. Новым наркомом вместо К. Е. Ворошилова стал С. К. Тимошенко. Василевский, которому было присвоено звание комдива, был назначен первым заместителем начальника оперативного отдела. В этой должности под руководством Б. М. Шапошникова, а затем сменивших его на посту начальника Генштаба К. А. Мерецкова и Г. К. Жукова он участвовал в разработке оперативного плана будущей «большой войны» с Германией и ее сателлитами, угроза агрессии со стороны которой становилась все более реальной. В ноябре 1940 г. Василевский был включен в состав советской делегации, выезжавшей на переговоры в Берлине. «Все члены делегации, — вспоминал Василевский, — вынесли общее впечатление от поездки: Советский Союз должен быть, как никогда, готов к отражению фашистской агрессии».
Вскоре после начала Великой Отечественной войны, в августе 1941 г., Василевский был назначен заместителем начальника Генштаба, начальником Оперативного управления. С этого момента он регулярно стал участвовать в заседаниях Ставки, ежедневно сопровождал Шапошникова во время совещаний последнего с Верховным главнокомандующим И. В. Сталиным. «Мы в то время говорили о себе больше в критическом духе, — писал Александр Михайлович потом в мемуарах, — и не всегда обращали должное внимание на то, какое мужество и отвагу проявляли советские воины в борьбе с врагом… Начало войны было не только периодом, когда наша армия переживала неудачи. Она в те дни проявила и волю к борьбе, стойкость, героизм».
В октябре 1941 г. из Москвы было объявлено осадное положение, началась эвакуация правительственных учреждений. Эвакуировался и Генеральный штаб. При Ставке была оставлена оперативная группа из десяти человек, возглавить которую было поручено Василевскому. В самые тяжелые дни битвы за Москву он, по сути, не отходил от Сталина, выполняя огромный объем работы по анализу изменений на фронте и выработке оперативно-стратегических предложений, на основе которых принимались решения. О значимости работы группы Василевского при Ставке свидетельствует следующий факт: как вспоминал Александр Михайлович, «Сталин сам установил для меня отдых от 4 до 10 часов утра и проверял, выполняется ли это его требование.
Случаи нарушения вызывали крайне серьезные и в высшей степени неприятные для меня разговоры». 28 октября Василевскому было присвоено звание генерал-лейтенанта.
Генеральный штаб возвратился в Москву в конце ноября, включившись в подготовку контрнаступления, однако, поскольку Б. М. Шапошников заболел, обязанности начальника Генштаба были временно возложены Сталиным на Василевского.
С июня 1942 г. до февраля 1945 г. Василевский возглавлял Генеральный штаб, будучи одновременно (с октября 1942 г.) заместителем наркома обороны СССР. Принимал участие в разработке и реализации крупнейших стратегических операций Великой Отечественной войны.
Совместно с Г. К. Жуковым стоял у истоков замысла по окружению и разгрому немецко-фашистских войск под Сталинградом. В ходе операции «Уран» в качестве представителя Ставки ВГК координировал действия советских фронтов. В критический момент сражения, когда немцы предприняли попытку деблокировать армию Паулюса контрударом группировки Манштейна, Василевский добился принятия и осуществления решения переключить 2-ю гвардейскую армию на Котельническое направление для срыва замысла врага, несмотря на сомнения Верховного и категорические возражения К. К. Рокоссовского и Н. Н. Воронова. В январе 1943 г.
Василевский координировал действия советских фронтов в успешной наступательной операции на Верхнем Дону.
Вклад Генерального штаба и лично А. М. Василевского в перелом событий на фронте был настолько значительным, что Сталин в начале 1943 г. дважды присваивал ему очередные звания, сначала генерала армии, а спустя всего месяц — Маршала Советского Союза.