We prove that all Gibbs states of the q-state nearest neighbor Potts model on Z^2 below the critical temperature are convex combinations of the q pure phases; in particular, they are all translation invariant. To achieve this goal, we consider such models in large finite boxes with arbitrary boundary condition, and prove that the center of the box lies deeply inside a pure phase with high probability. Our estimate of the finite-volume error term is of essentially optimal order, which stems from the Brownian scaling of fluctuating interfaces. The results hold at any supercritical value of the inverse temperature.