The politician Themistocles, with a power base firmly established amongst the poor, filled the vacuum left by Miltiades's death, and in the following decade became the most influential politician in Athens. During this period, Themistocles continued to support the expansion of Athens' naval power. The Athenians were aware throughout this period that the Persian interest in Greece had not ended, and Themistocles's naval policies may be seen in the light of the potential threat from Persia. Aristides, Themistocles's great rival, and champion of the zeugites (the 'upper hoplite-class') vigorously opposed such a policy.

In 483 BCE, a vast new seam of silver was found in the Athenian mines at Laurium. Themistocles proposed that the silver should be used to build a new fleet of triremes, ostensibly to assist in a long running war with Aegina. Plutarch suggests that Themistocles deliberately avoided mentioning Persia, believing that it was too distant a threat for the Athenians to act on, but that countering Persia was the fleet's aim. Fine suggests that many Athenians must have admitted that such a fleet would be needed to resist the Persians, whose preparations for the coming campaign were known. Themistocles's motion was passed easily, despite strong opposition from Aristides. Its passage was probably due to the desire of many of the poorer Athenians for paid employment as rowers in the fleet. It is unclear from the ancient sources whether 100 or 200 ships were initially authorised; both Fine and Holland suggest that at first 100 ships were authorised and that a second vote increased this number to the levels seen during the second invasion. Aristides continued to oppose Themistocles's policy, and tension between the two camps built over the winter, so the ostracism of 482 BCE became a direct contest between Themistocles and Aristides. In what Holland characterises as, in essence, the world's first referendum, Aristides was ostracised, and Themistocles's policies were endorsed. Indeed, becoming aware of the Persian preparations for the coming invasion, the Athenians voted to build more ships than those for which Themistocles had asked. Thus, during the preparations for the Persian invasion, Themistocles had become the leading politician in Athens.