We have developed a method for estimating the magnitude of prehistoric earthquakes using displacement data that usually can be collected from paleoseismic investigations. This method is necessary because essentially all current magnitude estimates for prehistoric events rely on determining the total length of coseismic surface rupture, which is rarely measurable, or rely on segmentation scenarios, for which uncertainties cannot be quantified. Although surface rupture length is a better predictor of magnitude than displacement for historic earthquakes, paleoseismic investigations are better at providing measurements of the amount of displacement at a site along a fault. The key to our method is to incorporate the variability in displacement observed in 14 modern events, which allows a formal uncertainty in magnitude to be assigned to prehistoric ruptures. We show how multiple measurements along a preserved fraction of a rupture can be combined to reduce the uncertainty in the estimate of magnitude. Our analysis shows that uncertainty asymptotically approaches the natural variability of ruptures, so 5 to 10 displacement measurements are sufficient to characterize paleomagnitude. We conclude that sampling of scarps with lengths of even 10% of the original rupture can provide magnitude values that reasonably estimate the earthquake. Tests of the method, using randomly sampled data from the 1992 Mw 7.3 Landers and 1954 Ms 6.8 Dixie Valley earthquakes, provide close approximations of the actual magnitudes.