Спартанцы, впрочем, оказали великие почести Фемистоклу. Они пригласили его в Спарту, торжественно увенчали его там вместе с Эврибиадом, подарили ему великолепную колесницу, какую только можно было найти в Спарте, а когда он возвращался домой, его торжественно провожали до границы 300 спартанских всадников. Заслуги Фемистокла, конечно, не могли быть помрачены; вся Эллада видела в нем своего освободителя. Когда он явился на Олимпийских играх, вскоре после того открывшихся, никто не хотел более смотреть на состязавшихся. В продолжение целого дня все взоры были устремлены только на него; на него указывали с гордостью иностранцам при возгласах и рукоплесканиях, и он с сердечным удовольствием признавался своим друзьям, что получил награду за свои труды для Греции.

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

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

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