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