Пригласив Василевского к себе, командующий сказал:
— Я рекомендовал вас на учёбу в Академию Генерального штаба. У вас есть боевой стаж, отличная аттестация по службе, высшее военное образование. По словам наркома, этот первый отбор слушателей проводится под строгим контролем ЦК партии. — Дыбенко посмотрел на Василевского. — Ну, как, желаете учиться?
— Очень даже желаю! — выплеснул на одном дыхании Александр Михайлович.
— Тогда собирайтесь к отъезду. Срок — три дня! С вами поедет на учёбу и ваш коллега начальник оперативного отдела штаба полковник Трофименко...
Учёба в академии всецело захватила Василевского. В июле 1937 года слушателям был предоставлен отпуск, а потом их отправили на двухнедельную стажировку на корабли Военно-Морского Флота. Василевский попал на Балтийский флот. В Ленинграде в штабе округа он встретился с командиром 2-го ранга Дыбенко.
— Вы? — растерянно заморгал тот. — Никак не ожидал встретить вас здесь.
Василевский ответил, что прибыл на стажировку на боевые корабли, и, когда Дыбенко пригласил его в свой кабинет, Александр Михайлович рассказал ему о своей учёбе, о тех военачальниках, с кем довелось увидеться в стенах академии.
— А как ваш Игорь?
— Растёт! Моя Катя души в нём не чает. А старший сын Юрий живёт у моей первой жены Серафимы. Тот горит желанием стать военным. А вы тут командуете военным округом?
— Как видите. Я рад, что снова прибыл в город, где в семнадцатом получил боевое крещение. А принял я округ от командарма первого ранга Ивана Панфиловича Белова... Странно, но факт, — продолжал Дыбенко, — меня окружают одни герои. Приволжский военный округ я принял от Ивана Фёдоровича Федько, тоже героя Гражданской войны, а передал маршалу Тухачевскому. — Голос у Павла Ефимовича вдруг сорвался. — А его, как вы знаете, в июне расстреляли...
В кабинете повисла напряжённая тишина. Дыбенко смотрел куда-то в окно и пальцами щипал бороду. Было видно — его что-то мучило.
— Павел Ефимович, — первым заговорил Василевский, — вы были на суде по делу Тухачевского и других видных военачальников. Неужели и вправду маршал оказался врагом народа, как и его коллеги?
— Вы что, Александр, не верите в советское правосудие? — усмехнулся с издёвкой Дыбенко. — И Тухачевский, и его коллеги были связаны с фашистами. Якир учился в академии генерального штаба Германии, читал лекции о Красной Армии, Корк некоторое время исполнял обязанности военного атташе в Германии, их там немецкая агентура и завербовала.
«Я в это не верю!» — едва не сорвалось с уст Василевского. А вслух он спросил:
— Вам жаль Тухачевского?
— Он же оказался врагом народа, чего его жалеть? — едва не выругался Дыбенко. — Я бы сам его расстрелял, если бы мне поручил это дело товарищ Сталин.
Ох как заблуждался Павел Ефимович! Не знал он, что и над ним уже сгущались тучи. Палач-авантюрист Ежов вскоре обвинил Дыбенко в том, что он, будучи в Средней Азии, якобы «выболтал» секретные сведения о Красной Армии американцам, когда те приезжали туда с делегацией. Ежов утверждал, что Дыбенко немецкий агент, что в гостинице «Националь» он устраивал пьянки, встречался с подозрительными девицами и прочее. И услышал об этом Павел Ефимович от самого Ежова, когда был в Москве. Дыбенко не на шутку встревожился: что ещё придумает о нём этот карлик-палач? Прибыв в Ленинград, он сразу же написал личное письмо Сталину. «Дорогой тов. Сталин! — выводил он дрожащей рукой. — Решением Политбюро и Правительства я как бы являюсь врагом нашей Родины и партии. Я живой, изолированный в политическом отношении труп. Но почему, за что? Разве я знал, что эти американцы, прибывшие в Среднюю Азию с официальным правительственным заданием, с официальными представителями НКИД и ОГПУ, являются специальными разведчиками? В пути до Самарканда я не был ни одной секунды наедине с американцами... О провокаторском заявлении Керенского и помещённой в белогвардейской прессе заметке о том, что я якобы являюсь немецким агентом, — продолжал писать Дыбенко. — Так неужели через 20 лет честной, преданной Родине и партии работы белогвардеец Керенский своим провокаторством мог отомстить мне? Это ведь просто чудовищно! Две записки, имеющиеся у тов. Ежова, написанные служащими гостиницы «Националь», содержат известную долю правды, которая заключается в том, что я иногда, когда приходили знакомые ко мне в гостиницу, позволял себе вместе с ними выпить. Но никаких пьянок не было... Товарищ Сталин, я умоляю Вас дорасследовать целый ряд фактов дополнительно и снять с меня позорное пятно, которого я не заслуживаю».