The redshift distribution of the short-duration GRBs is a crucial, but currently fragmentary, clue to the nature of their progenitors. Here we present optical observations of nine short GRBs obtained with Gemini, Magellan, and the Hubble Space Telescope. We detect the afterglows and host galaxies of two short bursts, and host galaxies for two additional bursts with known optical afterglow positions, and five with X-ray positions (<6 radius). In eight of the nine cases we find that the most probable host galaxies are faint, R~23-26.5 mag, and are therefore starkly different from the first few short GRB hosts with R~17-22 mag and z<0.5. Indeed, we measure spectroscopic redshifts of z~0.4-1.1 for the four brightest hosts. A comparison to large field galaxy samples, as well as the hosts of long GRBs and previous short GRBs, indicates that the fainter hosts likely reside at z>1. Our most conservative limit is that at least half of the five hosts without a known redshift reside at z>0.7 (97% confidence level), suggesting that about 1/3-2/3 of all short GRBs originate at higher redshifts than previously determined. This has two important implications: (i) We constrain the acceptable age distributions to a wide lognormal (sigma>1) with tau~4-8 Gyr, or to a power law, P(tau)~tau^n, with -1<n<0; and (ii) the inferred isotropic energies, E_{gamma,iso}~10^50-10^52 erg, are significantly larger than ~10^48-10^49 erg for the low redshift short GRBs, indicating a large spread in energy release or jet opening angles. Finally, we re-iterate the importance of short GRBs as potential gravitational wave sources and find a conservative Advanced LIGO detection rate of ~2-6 yr^-1.