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