Очутившись в Вильне, беглый подьячий подал прошение польскому королю Яну Казимиру, и вскоре Григория приняли на польскую службу при канцлере Великого княжества Литовского, которым был тогда Христофор Сигизмунд Пац. Новому сотруднику положили годовой оклад в 100 рублей. Котошихин выучил польский язык и изменил свою фамилию; теперь он звался Иоганном Александром Селицким.

Но на новом месте перебежчик не прижился. В Посольском приказе ему уже доставались серьёзные дипломатические миссии, а поляки лишь выведывали у него сведения о российском войске. Челобитные, отправленные "Селицким" канцлеру и в Раду, оставались без ответа и без последствий. Он так и не был официально представлен Яну Казимиру. Так что летом 1665 года "Иоганн Александр" бежал из Польши в Силезию, затем в Пруссию и оттуда – в Любек. Из Любека осенью того же года Котошихин приплыл в Нарву. Эта одиссея дорого обошлась бывшему подьячему: он потратил все деньги, к тому же обморозил ноги.

В Нарве Григорий нашёл знакомого, купца Кузьму Афанасьевича Овчинникова, шведского подданного. Тот помог ему попасть на аудиенцию к генерал-губернатору Ингерманландии Якобу Иоганну фон Таубе. А Таубе смог узнать в жалком оборванце ранее увиденного в Стокгольме московского дипломатического курьера. 24 октября 1665 года генерал-губернатор распорядился выдать Котошихину гражданскую одежду и деньги на пропитание. С первым же курьером в Стокгольм было отправлено прошение беглеца о приёме на шведскую государственную службу.

Уже через месяц шведское правительство постановило выдать Котошихину 200 риксдалеров и привезти перебежчика в Стокгольм. Для этой цели в Нарву направили самого Адольфа Эберса. Тот прибыл вовремя: Котошихин в приступе ностальгии попытался увидеться с царским гонцом Михаилом Прокофьевым, с которым познакомился ещё в 1664 году под Смоленском. Но Прокофьев не только отказался встречаться с предателем, но и сообщил о том, что изменник находится в Нарве новгородскому воеводе князю Василию Григорьевичу Ромодановскому Меньшому. А князь потребовал от Таубе выдать перебежчика и даже прислал в Нарву стрелецкого сотника Ивана Репнина. Подобные случаи были предусмотрены Кардисским миром, и проигнорировать требования Ромодановского шведы не могли.

Так что пришлось Таубе импровизировать: Котошихина посадили в тюрьму, после чего заявили Репнину, что выдать заключённого невозможно. А когда в Нарву приехал Адольф Эберс с деньгами и разрешительными документами, они на пару с генерал-губернатором инсценировали побег Котошихина из тюрьмы.

5 февраля 1666 года Котошихин прибыл в Стокгольм. Ему устроили аудиенцию у малолетнего Карла XI и в регентском совете, после чего выдали деньги на обустройство. Перебежчик обратился в лютеранство. Через некоторое время его приняли в штат архива Канцелярии. Котошихин начал писать труд о России в царствование Алексея Михайловича по заказу шведского правительства.

В конце 1666 года перебежчик поселился в южном предместье Стокгольма Сёдермальме у служившего в той же самой Канцелярии переводчика с русского языка Даниила Анастасиуса, скорее всего – тоже родившегося в России. Первые полгода хозяин и квартирант дружили. Но потом Даниил Анастасиус получил очень хорошо оплачиваемую подработку: он переводил русским купцам в Стокгольме. Шальные деньги хозяин квартиры спускал в кабаках, ничего не давая жене на домашнее хозяйство. Через несколько дней такого загула жена Анастасиуса, Мария Фалентинсдоттер, ушла.

25 августа 1667 года Котошихин помирил супругов, но уже вечером между хозяином и квартирантом произошла ссора, после которой Григорий тяжело ранил кинжалом или стилетом Даниила Анастасиуса, а также его свояченицу. Девушка выжила, но Анастасиус умер ночь с 8 на 9 сентября. Так что 10 сентября Мария Фалентинсдоттер подала на Котошихина в суд. Беглеца из России судили и 26 сентября 1667 года приговорили к смертной казни.