Вскоре состоялась дуэль Федора Толстого с другом Брунова Александром Нарышкиным, сыном московского обер-церемониймейстера, проживавшего на Пречистенке, 16. Ссора офицеров произошла, как обычно, за карточным столом. Покупая карту, Нарышкин сказал графу Толстому: «Дай туза». Граф Толстой положил карты, засучил рукав и, выставив кулак, сказал: «Изволь». Шутка Толстого заключалась в двояком толковании слов «дать туза», т. е. «отмутузить».
Нарышкин обиделся на грубую неразборчивую шутку, бросил карты и выскочил из комнаты. Он твердо намеревался прикончить «кровавого бретера», но погиб в этой дуэли сам. Убив Нарышкина, Толстой бежал из Москвы и долго путешествовал в составе морской экспедиции И. Ф. Крузенштерна. Поговаривали, что во время кругосветного плавания в одном из портов граф Толстой купил себе самку орангутанга. Вскоре, во время стоянки на островах, он завел себе еще одного друга – туземного царя Танега, которого «дрессировал как собаку», кидая ему щепку в море и заставляя «несчастного» приносить ее обратно
.Поговаривали, что граф Толстой, вождь и орангутанг, с утра запершись в каюте, целый день распивали ром, после чего ночью Танега отправился на остров и привез с собой очаровательных дикарок. Радостные матросы стали заниматься любовью прямо на палубе, а на корме стоял голый Федор Толстой и улыбался.
Через несколько дней разгульный граф напоил корабельного священника «до положения риз» и, когда святой отец заснул на палубе, припечатал его бороду сургучом к полу казенной печатью. Священник проснулся и попытался встать, но увидел над собой графа, который сообщил ему, что святость казенной печати нарушать нельзя. Пришлось отрезать поповскую бороду под самый корешок.
Капитан корабля, не выдержав буйных и несносных проказ графа, высадил Толстого вместе с его обезьяной на Камчатке, откуда он перебрался на один из Алеутских островов, где был с почетом встречен аборигенами, которые предлагали ему стать их царем. Некоторое время граф жил среди индейцев, покрыл свое тело татуировками, научил алеутов делать вино из диких ягод и играть в карты. Поговаривали, что он выиграл у местного вождя в карты его внучку и сам остров. По рассказам бесстрашного путешественника, его подобрало у Аляски торговое судно и доставило в Петропавловск, из которого он добирался до Петербурга по суше на телегах, санях, а отчасти и знаменитого мореплавателя изрядную долю славы. Тогда к нему и приклеилось прозвище Американец.