В августе 1919 г. в связи с приближением к Туле белогвардейских войск генерала А. И. Деникина Тульская губерния была объявлена на военном положении. Василевского назначили сначала командиром роты, затем — батальона, а уже в октябре — вновь сформированным 5-м стрелковым полком Тульской стрелковой дивизии. В боях с деникинцами полку участвовать не пришлось, так как прорваться к Туле им не удалось. В декабре 1919 г. Тульская дивизия (48-я стрелковая) была направлена на Западный фронт, где участвовала в войне с Польшей. По просьбе Василевского, считавшего, что у него недостаточно боевого опыта, перед началом боевых действий его переместили на должность помощника (заместителя) командира полка, а затем назначили командиром отдельного батальона. После подписания мирного договора с Польшей дивизия, в которой служил Василевский, участвовала в борьбе с бандами С. Булак-Балаховича.
После Гражданской войны Василевский возглавлял дивизионную школу младшего командного состава, а затем четыре года служил командиром 143-го Краснознаменного полка. В 1926 г. прошел годичное обучение на отделении командиров полков стрелково-тактических курсов «Выстрел». В 1928 г. он был назначен командиром 144-го полка, считавшегося в дивизии отстающим, слабым по дисциплине и подготовке. Через два года на дивизионной инспекторской проверке полк занял первое место.
В этот период на перспективного командира полка обратил внимание В. К. Триандафиллов — начальник оперативного управления и заместитель начальника штаба РККА, один из крупнейших советских военных теоретиков того времени, с чьим именем связывается разработка теории глубокой операции, наметившей способы наступательных действий оснащенных современной военной техникой (танками и авиацией) войск. Триандафиллов стажировался в должности командира корпуса, где служил А. М. Василевский. «Как командир 144-го полка я в течение двух лет фактически едва ли не постоянно учился и работал под его руководством», — свидетельствовал Александр Михайлович. По инициативе Триандафиллова в 1931 г. Василевский был приказом наркома обороны переведен в Москву, в центральный аппарат, и назначен в Управление боевой подготовки РККА. Затем, в 1934–1936 гг., служил начальником отдела боевой подготовки штаба Приволжского военного округа, а осенью 1936 г. зачислен слушателем в только что созданную Академию Генерального штаба. Многие сокурсники Василевского из этого, первого набора академии стали выдающимися полководцами и вписали свои имена в летопись Великой Отечественной войны: А. И. Антонов (начальник Генерального штаба на завершающем этапе войны), командующие фронтами И. X. Баграмян, Н. Ф. Ватутин, Л. А. Говоров, П. А. Курочкин, начальники штабов фронтов М. В. Захаров, М. И. Казаков, Г. К. Маландин, Л. М. Сандалов, командармы К. Д. Голубев, С. Г. Трофименко и др.
В 1937 г. в результате «чистки» в Красной Армии образовалось много вакансий, на замещение которых, не завершив обучения, направлялись слушатели академии. В августе 1937 г. Василевский был неожиданно назначен начальником кафедры тыла академии, а через месяц — начальником отделения оперативной подготовки высшего комсостава Генерального штаба РККА. «Тогда я, конечно, не знал, что в стенах Генштаба мне будет суждено провести ряд лет, заполненных сложной работой, самой трудной в моей жизни», — написал Александр Михайлович впоследствии в мемуарах.