По окончании института 1 сентября 1939 г., в день начала Второй мировой войны, Михаил был зачислен на службу в 5-е управление РККА, как в то время называлась советская военная разведка. А уже в начале октября того же года направлен для прохождения разведывательной подготовки в индивидуальном порядке в отделение разведотдела штаба Западного особого военного округа в город Белосток. Подготовка включала в себя изучение двух иностранных языков, радио- и фотодела, шифров. Заниматься приходилось ежедневно, с утра до позднего вечера, практически без выходных. Программа подготовки была рассчитана на 18 месяцев. Планировалось, что в конце июня 1941 года он должен был нелегально перебраться в Польшу, а затем, обзаведясь там польскими документами, попытаться осесть в Германии. Однако планам руководства не суждено было реализоваться. Когда подготовка разведчика была практически завершена, началась Великая Отечественная война.

Застигнутый вторжением немецких войск в Белостоке, Михаил вместе с другими сотрудниками разведотделения выходил из окружения, прорывался к своим…

В конце июля 1941 года Михаил был направлен в распоряжение разведотдела штаба Западного фронта в район Вязьмы, на станцию Касня.

В качестве заместителя командира группы разведчиков он до декабря 1941 года находился за линией фронта — в Великих Луках и Невеле. Члены группы вели разведку по дислокации и передвижению частей противника, минировали дороги, разрушали средства связи, карали предателей Родины.

В начале сентября 1942 года Михаил в составе разведывательно-диверсионного отряда специального назначения был выброшен на парашюте в районе города Барановичи Брестской области. За участие в боевых операциях награжден орденом Красной Звезды.

В общей сложности в тылу врага М. Федоров провел более 27 месяцев. Научился переносить трудности, ориентироваться в сложной обстановке, в совершенстве овладел радиоделом, приобрел навыки конспирации, усовершенствовал немецкий и польский языки. Опыт военных лет очень помог ему в последующей разведывательной работе.

После возвращения в Москву из-за линии фронта в августе 1944 года М. Федоров был откомандирован в распоряжение Главного разведывательного управления Генерального штаба Красной Армии. Он прошел необходимую подготовку и в августе 1945 года был направлен на нелегальную работу в Англию. Работал там в дипломатическом представительстве одной из зарубежных стран. Передавал в Центр важную информацию военно-политического характера.

Однако спустя полтора года из-за нелепой случайности разведчику пришлось прекратить командировку. А произошло вот что. В один из обыденных дней Михаил шел по коридору учреждения, в котором работал, и вдруг в его противоположной стороне увидел свою знакомую — бывшую преподавательницу из Белостока, у которой брал уроки иностранного языка. Непосредственного контакта удалось избежать, однако Михаил не был уверен, что женщина его не заметила. На другой день он выяснил, что преподавательница находилась в Англии в командировке и посетила посольство по своим личным делам. В Москву ушла радиограмма о случившемся. Центр решил не рисковать разведчиком…

Уже будучи в Москве, в середине 1947 года М. Федоров переводится из военной разведки на работу в Комитет информации при Совете Министров СССР (так в то время называлась внешняя разведка госбезопасности) и начинает напряженно готовиться к выполнению нового задания за границей. Но в планы подготовки вновь вмешался случай.

Из воспоминаний М. Федорова:

«Захожу как-то в столовую. Очередь небольшая, но я куда-то спешил. Вижу — стоят мои коллеги, я к ним:

— Предупреждали, что я буду? — а сам делаю знаки, мол, выручайте. Те только собрались ответить, как сзади раздался тонкий голосок:

— Нет, не предупреждали.

Оборачиваюсь и… встречаю взгляд жгучих черносмольных глаз, смотрящих на меня с вызовом и укором.

Так я познакомился с Галей…»

Галина Ивановна Маркина (в замужестве — Федорова) родилась 17 февраля 1920 г. в городе Саратове в рабочей семье. Отец был электромонтером-самоучкой. Позднее, после прохождения профессиональной подготовки, он получил должность директора мельницы, где работала и мать Галины. Сразу после революции вступил в партию большевиков. Последние годы жизни находился на партийной работе.

После смерти отца в 1932 году матери стало очень трудно воспитывать четверых детей: старшей сестре Гали было в то время 14 лет, младшим братьям — менее 10.

С 12 лет Галина воспитывалась у тети — сестры отца, которая проживала в Москве. В 1937 году девушка окончила школу-десятилетку. Стала работать на технической должности в Наркомфине СССР и одновременно учиться на вечернем факультете Московского высшего технического училища имени Н.Э. Баумана.

В январе 1939 года по путевке комсомола Галина пришла в органы государственной безопасности. Вначале работала в Транспортном управлении НКВД, занималась техническими вопросами, но привлекалась и к выполнению отдельных оперативных заданий.

В годы Великой Отечественной войны Галина находилась в распоряжении Группы особого назначения 4-го главного управления НКВД, занимавшейся подготовкой кадров для работы в подполье в тылу врага. Во время войны ей приходилось выполнять тяжелые и ответственные задания. Довелось также ухаживать за ранеными бойцами в подшефном военном госпитале, который в ту пору находился на 3-й Мещанской улице. Ночные дежурства, подмена санитарок, чтение газет и личных писем раненым — все это в выкраиваемые часы от основной работы, за счет отдыха. Война закалила Галину как будущего нелегального разведчика.

В 1946 году Галина окончила двухгодичные курсы иностранных языков при Высшей школе Министерства государственной безопасности СССР. Ей предложили перейти на работу во внешнюю разведку, в подразделение, которое занималось разведкой с нелегальных позиций. Беседовал с ней начальник нелегальной разведки полковник Александр Михайлович Коротков.

Галина Ивановна вспоминала, что на нее произвели большое впечатление дружелюбие и простота в общении со стороны Короткова, располагавшая к откровенности манера вести разговор.

После беседы, когда вопрос в принципе был решен, Александр Михайлович пошутил:

— Глядя на нее, никто не подумает, что она может заниматься разведкой.

«Это был камушек в мой огород. Причиной, видимо, являлся мой невысокий рост, неброский, скромный внешний вид».

Что привело молодую девушку в разведку? Об этом Галина Ивановна рассказывает:

«Мое представление о такого рода деятельности, как и у многих, было весьма скудным. Слышала, что туда отбирают особо способных сотрудников, что подготовка длится очень долго, что сама работа растягивается на годы и годы. Кроме того, требуется глубокое знание иностранных языков. Тут я имела плюс: языки мне давались легко, я много читала, переводила даже просто так, для себя. Ну и, конечно, волновало, подойду ли для такой службы? После обстоятельной и очень дружелюбной беседы с начальником нелегальной разведки полковником Александром Михайловичем Коротковым вопрос был решен.

На работу в разведку я пошла сознательно, с полным пониманием значения этой службы для государства и той ответственности, которую приняла на себя. Ни в то время, ни в последующем у меня не возникало ни малейших колебаний или запоздалых сомнений в правильности избранного в молодости пути. Я счастлива от того, что разведка стала делом всей моей жизни.

Вскоре произошли приятные изменения в личном плане. Как подарок судьбы появился он — Михаил. Сильный, добрый, чуткий, верный и надежный друг. С первых дней знакомства возникло ощущение, как будто мы знали друг друга сотню лет…»

Молодые люди решили пожениться, а сотрудники Центра… вынуждены были изменить планы подготовки Михаила и начали разрабатывать вариант их совместной поездки на нелегальную разведывательную работу.

Среди сотрудников внешней разведки выражение «Нелегалами не рождаются, ими становятся» воспринимается как истина, не требующая доказательства. Просто в какой-то момент разведке, исходя из возникших или порученных задач, требуется конкретный человек, пользующийся особым доверием, обладающий определенными личными и деловыми качествами, профессиональной ориентацией и необходимым жизненным опытом для того, чтобы направить его на работу в конкретный регион земного шара. Для Федоровых таким регионом была Австралия.