How much does it cost to teleport?

We show that the entropy of entanglement of a state characterizes its ability to teleport. In particular, in order to teleport faithfully an unknown quantum $N$-state, the two users must share an entangled state with at least $\log_2 N$ bits entropy of entanglement. We also note that the maximum capacity for a mixed state ${\cal M}$ to teleport equals the maximum amount of entanglement entropy that can be distilled out from ${\cal M}$. Our result, therefore, provides an alternative interpretation for entanglement purification.