We study the problem of extracting EPR pairs from a general source of entanglement. Suppose Alice and Bob share a bipartite state R which is "reasonably close" to perfect EPR pairs. The only information Alice and Bob possess is a lower bound on the fidelity of R and a maximally entangled state. They wish to "purify" R using local operations and classical communication and output a state that is arbitrarily close to EPR pairs. We prove that on average, Alice and Bob cannot increase the fidelity of the input state significantly. On the other hand, there exist protocols that may fail with a small probability, and otherwise will output states arbitrarily close to EPR pairs with very high probability. These protocols come from the "purity-testing protocols" of Barnum et al.