Когда именно совершился побег, неизвестно. Вероятно, это произошло на рубеже 1664 и 1665 гг. В Вильне беглый подьячий подал прошение на имя польского короля Яна-Казимира и был принят на службу канцлера Великого княжества Литовского. Годовой оклад Котошихина составил впятеро большую сумму, чем в России, – 100 рублей. Фамилию подьячий сменил и отныне звался Яном-Александром Селицким.
Впрочем, заурядная служба в польской провинции, по-видимому, не устраивала Котошихина. После того как несколько его писем королю остались без ответа, он летом 1665 г. бежал из Польши в Силезию, откуда пробрался в Пруссию и оттуда в Любек. В октябре 1665 г. Котошихин на корабле прибыл из Любека в Нарву. Скитания по Европе не пошли ему на пользу – до Нарвы он добрался с обмороженными ногами, голодный, оборванный, без копейки денег. К счастью, в Нарве Котошихин встретил старого знакомого, шведского подданного Кузьму Овчинникова, который отвел Григория к губернатору города Якобу Таубе. Тот, с трудом узнав в нищем оборванце бывшего московского дипломата, пять лет назад встреченного в Стокгольме, распорядился выдать русскому одежду и небольшую сумму денег.
По всей видимости, к этому времени Котошихин сильно раскаивался в своей эмиграции, так как, узнав о том, что в Нарве находится его старый сослуживец Михаил Прокофьев, поспешил к нему. Но тот не только не стал общаться со знакомцем, но и немедленно сообщил новгородскому воеводе князю В.Г. Ромодановскому о перебежчике. Воевода тут же потребовал у шведов выдать «вора» и отрядил для этого в Нарву стрелецкого капитана. Но шведы, как выяснилось, выдавать Котошихина вовсе не собирались. Для безопасности его посадили в тюрьму, где и держали до 9 декабря 1665 г., когда в Нарву прибыл старый знакомый подьячего – Адольф Эберс. Он привез бумагу, разрешавшую Котошихину переезд в Стокгольм и поступление на государственную службу.
5 февраля 1666 г. Котошихин прибыл в столицу Швеции. Его принял король Карл XI, который распорядился выдать эмигранту 150 далеров серебром. В том же году Григорий Карпович приступил к работе над обширной запиской о России, которая была заказана ему шведским государственным канцлером Магнусом Делагарди. Шведские власти были весьма заинтересованы в работе Котошихина и 29 ноября 1666 г. назначили ему немалое жалованье – 300 далеров серебром в год. Поселился Котошихин в Стокгольме в доме старого знакомого, переводчика Даниила Анастасиуса, с которым у него сложились теплые отношения.
Все испортил, как это часто бывает, обыкновенный алгоколь. 25 августа 1667 г. Анастасиус поссорился с женой, после чего Котошихин по ее просьбе помирил супругов. Домовладелец с постояльцем вместе отправились в город, чтобы купить в знак примирения кольцо. Вернулись оба вдрызг пьяные и начали выяснять отношения. Анастасиус обвинял