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