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 ( \lesssim 6 ^ { \prime \prime } radius ) . In eight of the nine cases we find that the most probable host galaxies are faint , R \approx 23 - 26.5 mag , and are therefore starkly different from the first few short GRB hosts with R \approx 17 - 22 mag and z \lesssim 0.5 . Indeed , we measure spectroscopic redshifts of z \approx 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 \gtrsim 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 \gtrsim 1 ) with \tau _ { * } \sim 4 - 8 Gyr , or to a power law , P ( \tau ) \propto \tau ^ { n } , with -1 \lesssim n \lesssim 0 ; and ( ii ) the inferred isotropic energies , E _ { \gamma, { iso } } \sim 10 ^ { 50 } -10 ^ { 52 } erg , are significantly larger than \sim 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 \sim 2 - 6 yr ^ { -1 } .