We present the first high-redshift Hubble diagram for Type II-P supernovae (SNe II-P) based on five events at redshift up to z ∼ 0.3. This diagram was constructed using photometry from the Canada-France-Hawaii Telescope Supernova Legacy Survey and absorption-line spectroscopy from the Keck Observatory. The method used to measure distances to these Supernovae is based on recent work by Hamuy & Pinto and exploits a correlation between the absolute brightness of SNe II-P and the expansion velocities derived from the minimum of the Fe II λ5169 P Cygni feature observed during the plateau phases. We present three refinements to this method that significantly improve the practicality of measuring the distances of SNe II-P at cosmologically interesting redshifts. These are an extinction correction measurement based on the V-I colors at day 50, a cross-correlation measurement for the expansion velocity, and the ability to extrapolate such velocities accurately over almost the entire plateau phase. We apply this revised method to our data set of high-redshift SNe II-P and find that the resulting Hubble diagram has a scatter of only 0.26 mag, thus demonstrating the feasibility of measuring the expansion history, with present facilities, using a method independent of that based on supernovae of Type Ia. © 2006. The American Astronomical Society. All rights reserved.