For a constant $\epsilon$, we prove a $\poly(N)$ lower bound on the (randomized) communication complexity of $\epsilon$-Nash equilibrium in two-player $N\times N$ games. For $n$-player binary-action games we prove an $\exp(n)$ lower bound for the (randomized) communication complexity of $epsilon$-Nash equilibrium. The implications of these results on the rate of convergence of dynamics to Nash equilibria will be discussed.