В 1799 г. в возрасте 17 лет он в первый раз дрался на дуэли с офицером, отчитавшим его за нарушение дисциплины. В некоторых воспоминаниях значится, что его разжаловали в солдаты.

В 1803 г. Федор Толстой отправился в плавание в качестве члена команды шлюпа «Надежда», который входил в состав экспедиции под руководством И.Ф. Крузенштерна — это было первое кругосветное путешествие кораблей под российским флагом. Марья Каменская, дочь его двоюродного брата, пишет, что Толстой таким образом ловко избежал очередного наказания в Преображенском полку. По ее словам, он выдал себя за своего двоюродного брата-тезку, который числился в составе экипажа, но не желал плыть, так как страдал морской болезнью.

Кроме исследовательских целей, экспедиция должна была также помочь установлению дипломатических и экономических связей России с Японией, для чего в состав команды входила большая дипломатическая делегация во главе с Николаем Резановым. Курс «Надежды» проходил через Балтийское море и Атлантический океан, мимо Канарских островов и Бразилии, после чего корабль обогнул мыс Горн и пошел по Тихому океану в сторону Японии, делая остановки на Маркизских и Гавайских островах. После чего «Надежда» посетила Японию и Камчатку, а «Нева» взяла курс на остров Ситка. Встретившись в Макао, корабли через Индийский, а затем Атлантический океан и Балтийское море вернулись в Кронштадт. В итоге, плавание продолжалось более трех лет, с 7 августа 1803 г. по 19 августа («Нева») и 30 августа («Надежда») 1806 г.

Находясь на борту, Толстой то и дело провоцировал ссоры с другими членами команды, в том числе с самим капитаном. Позволял себе злые шутки в адрес членов команды: так, однажды он напоил сопровождавшего «Неву» священника и, когда тот лежал мертвецки пьяный на полу, приклеил его бороду к доскам палубы сургучом, запечатав казенной печатью. А чтобы пришедший в себя батюшка не смог освободиться — Толстой напугал его, сказав, что печать ломать нельзя. В итоге бороду пришлось отрезать. В другой раз Толстой в отсутствие Крузенштерна прокрался в его каюту с любимцем команды, ручным орангутаном, которого Толстой купил при одной из остановок на островах в Тихом океане. Там он достал тетради с записями Крузенштерна, положил сверху лист чистой бумаги и стал показывать обезьяне, как заливать чернилами бумагу. Затем он оставил орангутана в каюте одного. Когда Крузенштерн вернулся, все его записи оказались уничтожены.

Неудивительно, что Ф. Толстого часто сажали под арест, но это не помогало. Понимая, что ситуация вот-вот дойдет до смертоубийства, Крузенштерн высадил хулигана на Камчатке, откуда тот добрался до одного из Алеутских островов или же на остров Ситка, где провел несколько месяцев среди аборигенов Аляски — племени тлинкит. Во время пребывания Толстого на Ситке его тело украсили многочисленные татуировки, которые он позже с гордостью демонстрировал любопытствующим. Что же до орангутана, которого вместе с Толстым высадили на сушу, по одной из версий, живя на Камчатке, Толстой с ним сожительствовал, по другой — съел.

По рассказам Толстого, его подобрало у Аляски торговое судно и доставило в Петропавловск, из которого Толстой добирался до Петербурга по суше на телегах, в санях, а отчасти и пешком. Одно из немногих письменных свидетельств этой одиссеи находится в «Записках» бытописца Вигеля, вышедших в свет в 1892 г. Вигель, путешествовавший в начале XIX в.