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

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

Но и в Ионии Фемистокл был не совсем в безопасности, потому что царь персидский оценил в 200 талантов его голову, а греки все еще преследовали его. Он бежал в Эгу, в Эолии, к своему другу Никогену, который скрывал его у себя некоторое время и потом в закрытой повозке, какие обыкновенно употреблялись для перевозки женщин, отправил в самую Персию. Если у проводников в дороге спрашивали, кого везут они в повозке, то отвечали: девицу-гречанку к царскому двору. Никоген был знаком с вельможами персидского двора и рекомендовал своего гостя одному знатному персу в Сузе; из Сузы Фемистокл отправил к царю Артаксерксу, сыну и наследнику Ксеркса, следующее письмо: «Я, Фемистокл, пришел к тебе — тот самый Фемистокл, который, пока принужден был защищаться против нападений твоего отца, более всех греков нанес вреда твоему дому, но еще больше сделал ему добра в то время, когда я сам находился в безопасности, а твой отец был принужден к бедственному отступлению. Такое благодеяние (услуги, оказанные им Ксерксу при Саламине) не должно быть забыто, тем более что я и теперь могу еще оказать тебе важные услуги. К тому же я пришел сюда потому, что греки преследуют меня за дружественное расположение к тебе. По истечении года я самому тебе открою, зачем я прибыл сюда».

Царь удивлялся уму этого человека и одобрил его план.