We have discovered a 716-hertz eclipsing binary radio pulsar in the globular cluster Terzan 5 using the Green Bank Telescope. It is the fastest spinning neutron star found to date, breaking the 24-year record held by the 642-hertz pulsar B1937+21. The difficulty in detecting this pulsar, because of its very low flux density and high eclipse fraction (approximately 40% of the orbit), suggests that even faster spinning neutron stars exist. If the pulsar has a mass less than twice the mass of the Sun, then its radius must be constrained by the spin rate to be <16 kilometers. The short period of this pulsar also constrains models that suggest that gravitational radiation, through an r-mode (Rossby wave) instability, limits the maximum spin frequency of neutron stars.