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