We study the design of a tax rule to redistribute income across heterogeneous workers optimally. The social planner faces uncertainty about the possible income choices available to each type of worker, and, therefore, cannot perfectly predict the income distribution induced by a given tax rule. In the face of this uncertainty, the planner maximizes her worst-case expected payoff. We show that using a progressive tax rule is optimal regardless of the planner’s preference for redistribution and that it is uniquely so under an additional richness assumption on the set of income choices that the social planner knows is available to workers. This result stands in contrast to the familiar zero-taxation-at-the-top result that arises generally (absent specific distributional assumptions) in the Bayesian optimal taxation model of Mirrlees (1971). To that extent, our robust approach to uncertainty about workers’ income possibilities provides a new foundation for progressive income taxation—-a feature that is prevalent in most existing tax systems—-that does not rely on parametric assumptions on the distribution of workers’ productivity, or on the social planner’s attitude toward income inequality.