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