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