Supernova simulations to date have assumed that during core collapse electron captures occur dominantly on free protons, while captures on heavy nuclei are Pauli-blocked and are ignored. We have calculated rates for electron capture on nuclei with mass numbers A=65-112 for the temperatures and densities appropriate for core collapse. We find that these rates are large enough so that, in contrast to previous assumptions, electron capture on nuclei dominates over capture on free protons. This leads to significant changes in core collapse simulations.