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

Для достижения дели необходимо было прибегнуть к хитрости. Фемистокл именно и был способен устроить это дело.

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

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

Спартанцы видели в Фемистокле своего величайшего врага и делали все, чтобы подорвать его влияние в Афинах и сделать его безвредным. Афиняне в этом случае шли навстречу их стремлениям. Характер Фемистокла был небезупречен: в нем было мало чувства законности, права и справедливости, его упрекали в насильственных действиях и продажности; к тому же со своими новыми широкими планами он не давал покоя народу, так что можно было опасаться, что он, пожалуй, еще вовлечет Афины в опасную войну со Спартой. Поэтому народ отступился от Фемистокла и обратился к более правдивому, спокойному Аристиду. Наконец (в 472) партии Кимона, поддерживаемой спартанцами, — Аристид же держался в стороне, — удалось посредством остракизма изгнать беспокойного и опасного человека.

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