В конце 1666 г. Котошихин поселился в южном предместье Стокгольма у русского толмача Даниила Анастасиуса. Анастасиус отличался склонностью к крепким напиткам, а во хмелю был буен и частенько поколачивал жену Марию Валентину, и она уходила от него. Котошихин пытался мирить их, и одна из попыток примирения закончилась пьяной ссорой и бытовым убийством. Вот как пишет об этом хорошо знавший Котошихина переводчик Улоф Баркхусен: «Анастасиус подозревал Селиц-каго в порочной связи с своей женой, однажды, быв оба дома в нетрезвом виде, они заспорили между собою: начались с обеих сторон упреки и брань, Селицкий в запальчивости гнева нанес Анастасиусу несколько смертельных ударов испанским кинжалом, который в это время имел при себе».
Вдова Анастасиуса потребовала наказать убийцу по всей строгости закона. Суд приговорил Котошихина к смертной казни через отсечение головы. Он признал свою вину, о помиловании не просил и в ноябре 1667 г. сложил голову на плахе. Перед казнью он принял лютеранство. «Так кончил жизнь свою Селицкий, муж русского происхождения, ума несравненного» — писал Баркхусен. После казни его тело было отвезено в Упсалу, где оно было анатомировано профессором медицины Улофом Рудбеком. Его скелет, нанизанный на медные и стальные проволоки, был выставлен в Анатомическом театре. В 1670 г. там его видел Саксен-Готский герцог Альбрехт. Где он находится сейчас, неизвестно.
В 1669 г. сочинение Котошихина было переведено на шведский язык Баркхусеном, с перевода было снято несколько копий. Подлинная рукопись Котошихина досталась шведскому ученому Ю.Г. Спарвенфельдту, знавшему русский язык. Он сделал на ней помету, в которой ошибочно назвал автора «Кошихиным». Спарвенфельдт передал рукопись в Упсальский университет, где она хранится и поныне. Скорее всего, первым из русских людей рукопись увидел А.И. Тургенев. Он считал, что со слов Густава III о ней впервые узнала Екатерина II. Однако эта версия не подтвердилась. В переписке короля с императрицей речь шла, очевидно, о списке Разрядной книги, хранящейся в библиотеке Упсальского университета.
Первооткрывателем сочинения Котошихина следует считать профессора Гельсингфорского университета С.В. Соловьева. В 1837 г. он обнаружил его шведский перевод в Государственном архиве Швеции, а в 1838 г. им был открыт и русский оригинал в библиотеке Упсальского университета и он скопировал его. Именно ему мы обязаны тем, что сочинение Котошихина стало одним из самых используемых и цитируемых источников по истории России XVII в. Впервые оно было издано Археографической комиссией в 1840 г. под названием: «О России в царствование царя Алексея Михайловича». В опубликованной в журнале «Москвитянин» рецензии на это издание было сказано: «Не только в XVIII веке, но и в XIX едва ли сыщется сочинение, которое бы обилием содержания, знанием дела и чистотою изложения могло равняться с сочинением подьячего Котошихина о России. Подьячий обнимает все отрасли государственного управления… повествует о самых существенных обычаях русской земли и бросает смелый взгляд на внутреннее устройство русского духа».
