Беда была в том, что изгнанник не имел возможности защищаться и был вынужден в письмах опровергать возводимую на него клевету. Но этого оказалось недостаточно, и он был заочно объявлен изменником. В Аргос были направлены люди, чтобы арестовать Фемистокла и доставить в народное собрание. Но они опоздали. После гибели Павсания Фемистокл ни на минуту не сомневался в том, какой приговор ему будет вынесен, и, не чувствуя себя в безопасности, решил бежать из Аргоса. Вскоре беглец объявился на острове Керкира. Но местные власти не хотели связываться со спартанцами и афинянами, поэтому отказали Фемистоклу в предоставлении политического убежища. Погоня шла по следу беглеца, и победитель персов был вынужден укрыться в Эпире, где правил его недоброжелатель царь Адмет. Но другого выхода у Фемистокла не было, его травили как волка на охоте, обкладывая со всех сторон. И здесь судьба повернулась лицом к изгнаннику. Адмет, в отличие от керкирян, проявил благородство и, когда спартанские и афинские посланцы потребовали выдать Фемистокла, ответил отказом. Он помог беглецу добраться до города Пидна в Македонии, откуда Фемистокл на грузовом корабле прибыл в Эфес. Наняв проводника из персов, афинянин отправился к царскому двору.
К этому времени в державе Ахеменидов произошли серьезные изменения. В результате дворцового заговора Ксеркс был убит, и на престол вступил его сын, Артаксеркс I. И было неизвестно, как он поведет себя по отношению к человеку, ставшему символом сопротивления Эллады персидскому нашествию. Но Фемистокл привык рисковать и пошел ва-банк, хотя ставкой в этой игре была его жизнь. В дороге он написал царю письмо, текст которого приводит Фукидид: «
Получив послание, Артаксеркс немало удивился, но решил не спешить, а выполнить все пожелания Фемистокла. Очевидно, что царь уже давно знал о том, каким образом афинский стратег оказывал услуги его отцу. Сам же Артаксеркс, по свидетельству Плутарха, помолился о том, «