Для достижения афинской гегемонии на море Фемистокл, казалось, был готов пойти на все. Плутарх пишет на сей счет: «…Он питал еще более широкие замыслы в отношении морского могущества Афин. После отступления Ксеркса флот эллинов, войдя в Пагасийскую гавань, зимовал там. И вот, Фемистокл, выступив перед афинянами в народном собрании, заявил, что им задумано некое дело, для них полезное и спасительное, но не подлежащее широкой огласке. Тогда афиняне приказали ему сообщить о деле лишь одному Аристиду и исполнить свой план, если последний выразит одобрение, после чего Фемистокл объявил Аристиду, что он имеет в виду сжечь верфь эллинов. Аристид, в свою очередь, выступив перед народом, заявил, что план Фемистокла столь же полезен для государства, сколь и беззаконен. Услышав это, афиняне велели Фемистоклу дело это оставить».

Не безынтересно, что многим позднее, когда к власти в Афинах пришли тираны, то построенную ораторскую кафедру на Пниксе они в отместку памяти о Фемистокле велели поставить так, чтобы та была повернута в сторону суши, ибо считали, что владычество над морем породило в Афинах демократию.

Так в понимании вершителей судеб Эллады слились воедино морское могущество, демократия и Фемистокл.

Однако с устранением угрозы персидского нашествия стало постепенно меняться и отношение к Фемистоклу. Его независимость, авторитет и популярность, помноженные на осознание своей значимости и интеллектуального превосходства над подавляющим большинством афинской аристократии и зависть последних, просто не могли не создать ему множество противников.

И снова обратимся к Плутарху: «…Так как клеветам уже начали из зависти охотно внимать и граждане, а Фемистокл часто напоминал в народном собрании о своих прежних заслугах, то он поневоле стал всем в тягость. „Что же, разве устаете вы получать по нескольку раз благодеяния от одних и тех же людей?“ — спрашивал он недовольных. Удручающе подействовала на народ и постройка храма Артемиды, которую Фемистокл назвал Аристобулой как бы в знак того, что наилучшие советы давал городу и всем эллинцам не кто иной, как он. Построена была эта святыня возле его дома в Мелите… Остракизму же подвергли Фемистокла несомненно с той целью, чтобы сокрушить его чрезмерно поднявшийся авторитет, как это обычно делалось со всеми, чье влияние считали тягостным и нарушающим демократическое равенство. Ибо изгнание остракизмом не было наказанием, а служило лишь успокоительным и облегчающим средством для зависти, которая находит радость в унижении выдающихся людей и выход своему озлоблению в таком их поругании».

Быть может, на этом бы все беды для Фемистокла и закончились, если бы в это время спартанцы не разоблачили предательство своего царя Павсания. Он командовал спартанским войском в знаменитой битве при Платеях, но затем вел тайную переписку с персами и, что самое страшное, хотел дать права граждан рабам-илотам. Героя Платей заживо замуровали в храме, где он и умер от голода. При обыске в его доме нашли несколько писем Фемистокла. Налаживая связи с персами, Павсаний хотел привлечь к своему делу и своего афинского друга. И хотя текст писем однозначно говорил за то, что последний участвовать в деле Павсания отказался, это дало повод к началу гонений на Фемистокла. Толпа быстро забывает своих вчерашних кумиров. Тех, кого еще вчера носили на руках, сегодня с таким же воодушевлением забрасывают камнями…

Для бывшего наварха началось время изгнаний. Он проживает в Аргосе, затем бежит от преследования своих бывших сограждан на Керкиру (Корфу), оттуда в Эпир, оттуда к царю молоссов Адмету. Тиран Сицилии Гиерон объявил за поимку беглеца, который когда-то, будучи на вершине афинской власти, очень насолил ему, фантастическую сумму денег — 200 талантов.