Постепенно болезнь отступила, и в конце 1922 года Быстролетов был отправлен Красным Крестом в Чехословакию, где открылись школы для белоэмигрантской молодежи. «Белогвардейцы-гимназисты, узнав, что я служил в Красном флоте и бежал от белых, приняли меня в штыки: в общежитии мне ночью пачкали одежду, плевали в меня и т. д., — пишет Быстролетов. — Эта травля крайне взвинтила мои нервы, и болезнь возвратилась в форме истерии и желания покончить с собой. В это время в СССР был голод, и заграничные газеты размазывали ужасы на все лады. Изолированный от окружающих, я жил только газетами, без конца читая о голоде, умирающих и прочее. Это усиливало психоз, в котором мне казалось, что умирает вся страна, а поэтому я должен немедленно вернуться домой и умереть вместе со всеми».
Обращение в советское консульство дало результат, и Быстролетов был отправлен в Ленинград для прохождения службы на Балтийском флоте. В Великих Луках он впервые оказался в лагере — всего лишь сортировочном лагере для военнопленных. Балтийский флот его не принял, и ему было предписано направиться в Новороссийск, но там работы не оказалось. Начался бюрократический футбол. Оставив надежду на власти, Быстролетов взял билет из Севастополя до Батума, повторяя ранее проделанный путь в поисках работы в портах. Не ведая того, он вступил на дорогу, которая в конце концов привела его в советскую разведку. Поворотный момент в его жизни не был отмечен каким-либо драматическим событием — он свершился внутри его — на психологическом, идейном уровне. Сам Быстролетов вспоминает об этом так:
«…Ночью на пароходе я однажды стал случайным свидетелем разговора двух пассажиров. Бывают события, которые определяют всю дальнейшую жизнь человека. Именно таким оказался для меня этот разговор. До этого жизнь моя была весьма сумбурной. Я много повидал, многое выстрадал, у меня не было времени подумать, осознать себя, жизнь, революцию, свой долг, свое будущее, будущее всей страны. В эту ночь два коммуниста лежа говорили об окончании Гражданской войны, о том, что голод быстро пройдет, что молодая страна будет возрождаться, главное сейчас — учеба: «учиться, чтобы потом строить одновременно добивая недобитых врагов». Я слушал как зачарованный, словно пробудившийся от долгой спячки. И я вдруг осознал себя. Ведь я ехал «умереть вместе со страной» — но страна, оказывается, не собиралась умирать. К тому же я отдохнул, море благотворно подействовало на мое физическое самочувствие, и я уже не испытывал ни малейшего желания умереть, я ощутил желание жить и бороться. Вспомнились эмигранты, плевавшие мне в тарелку с супом и ночью коловшие меня спящего булавками. Я осознал ошибочность моего отъезда за границу и нелепость последовавшего вскоре возвращения. Болезнь, очевидно, еще не прошла, и я пребывал в состоянии экзальтации. Я говорил себе, что должен искупить свою ошибку не работая грузчиком на желдороге, а борьбой с проклятыми эмигрантами — в стране свергнуты военные фронты, но фронт есть в Праге.
Я должен ехать туда и взять за горло эмигрантов».
Вот в таком состоянии «экзальтации» Быстролетов высадился в Батуми и провел там без денег и без еды несколько дней в ожидании какого-нибудь иностранного парохода. Когда таковой появился, он проскользнул через кордон пограничников и спрятался в вентиляционной трубе, просидев в ней без пищи и почти без воды на протяжении всего пути до Константинополя. В Константинополе он подкрепился отбросами из мусорных ям и на крышах поездов пересек Турцию, Грецию, Болгарию, Сербию, Венгрию, добравшись наконец до Праги. «Я был тощий как скелет и воспринимался окружающими как не вполне нормальный, — вспоминает Быстролетов. — Я явился в консульство и рассказал все, как есть. Консул с удивлением меня выслушал и заявил: «Вы если не шпион, то сумасшедший. Уйдите из консульства, иначе я позвоню в полицию!»
Эмигранты отнеслись к Быстролетову иначе. Узнав, что он приехал из СССР, их руководство предложило ему выступить с докладом и рассказать о голоде и о зверствах ЧК. Быстролетов согласился. Он решил сделать первый шаг в перетягивании эмиграции на свою сторону. В день выступления зал был набит битком — желающих увидеть и послушать «беженца из СССР, похожего на живой труп», было много.
«Я обрисовал истинные размеры голода, а затем сказал, что страна крепнет и будет крепнуть, что все эмигранты должны вернуться и искупить свои грехи перед СССР, иначе за границей они заживо сгниют. Враждебные же элементы должны быть раздавлены, — вспоминал позже свою наивную прямолинейность Быстролетов. — Разразился ужасный скандал, меня поволокли к дверям и наверняка убили бы, если бы не возникшая там сутолока, но так как каждый хотел меня ударить, то все друг другу мешали, и я остался жив (только получил рану ножницами)».
У отвергнутого советским консульством Быстролетова не оставалось другого выхода, как поселиться в эмигрантском общежитии, куда его определили чехословацкие власти. Он работал гробовщиком на кладбище и начал учиться на медицинском факультете Пражского университета. Но спокойной жизни у него не получилось. В общежитии его всячески преследовали, избивали, будили ночью электротоком, тыкая оголенными проводами в тело, и даже пытались выбросить с четвертого этажа («спасли меня длинные ноги, которыми я упирался в боковины окна»). «Я стал скрытным, — пишет Быстролетов, — сгруппировал вокруг себя единомышленников и повел активную борьбу с эмиграцией. Ярость охватила меня, я жил ненавистью».
Полпредство СССР в Праге обратило внимание на Быстролетова. Ему предоставили возможность получить советское гражданство. Он стал одним из руководителей Союза советских студентов в Чехословакии. Несомненно, что интерес к Быстролетову проявила прежде всего резидентура Иностранного отдела ОГПУ, одной из главных задач которого была работа по «белой линии» — разложение враждебно настроенной белой эмиграции и перетягивание колеблющихся на сторону Советского Союза. «Моей борьбой стали руководить, поверив в мою честность, — вспоминает Быстролетов. — Борьба из уличной и яростной стала более спокойной, но и более серьезной — мы стали разлагать эмигрантские организации изнутри нелегальными методами».
В 1924 году чехословацкая полиция дважды пыталась выдворить Быстролетова из страны, так как кое-что из его действий получило огласку. Чтобы не потерять полезного человека, резидент ИНО ОГПУ Днепров устроил Дмитрия Александровича на работу в Торгпредство. Быстролетов по всем своим данным и начальному опыту оперативной работы, видимо, весьма заинтересовал советскую разведку, и Днепров рекомендовал зачислить его в ряды кадровых сотрудников. Удобный случай познакомиться с ним представился Центру в апреле 1925 года. В Москве проходил 1-й Съезд пролетарского студенчества, на который Быстролетов и был командирован Полпредством в качестве зарубежного представителя. «К тому времени мне было лишь известно, — пишет Быстролетов, — что второй секретарь посольства — сотрудник ЧК и что Главное управление ЧК находится в здании на Лубянке».
Сам Быстролетов считает началом своей работы в разведке памятную для него беседу с Артуром Артузовым и Михаилом Горбом в конце апреля 1925 года. Он подробно описывает ее в своих неопубликованных воспоминаниях:
«В Праге меня предупредили, что в Москве со мной будут беседовать очень важные лица. И действительно, в конце апреля меня отвели в бывший долгоруковский особняк, в маленькую комнату, где на диване лежал одетым усталый сонный мужчина средних лет, а рядом, оседлав стул, положив руки на его спинку, сидел и курил мужчина помоложе, брюнет, с раскосыми глазами. Потом мне сказали, что лежал А.Х. Артузов, а сидел М. Горб. Рядом стоял еще один стул, и мне предложили сесть. Я не знал, кто эти люди и что они от меня хотят, но чувствовал, что это большие начальники и что от разговора с ними зависит моя будущая судьба. Мне шел тогда 25-й год, я был недурен собой и одет в свой лучший костюмчик, что особенно бросалось в глаза на фоне толстовок и тапочек московских студентов. На лице Горба отразилось явное недоброжелательство, он окинул меня мрачным взглядом и отвел глаза в сторону. Артузов, напротив, с видимым интересом принялся разглядывать меня и мой костюм, не скрывая доброжелательную улыбку.