A new technique is presented for determining the black hole masses of high-redshift quasars from optical spectroscopy. The new method utilizes the full-width at half-maximum (FWHM) of the low-ionization MgII emission line and the correlation between the broad-line region (BLR) radius and the continuum luminosity at 3000 Å. Using archival ultraviolet (UV) spectra it is found that the correlation between BLR radius and 3000-Å luminosity is tighter than the established correlation with 5100-Å luminosity. Furthermore, it is found that the correlation between BLR radius and 3000-Å continuum luminosity is consistent with a relation of the form RBLR~λL1/2λ, as expected for a constant ionization parameter. Using a sample of objects with broad-line radii determined from reverberation mapping it is shown that the FWHM of MgII and Hβ are consistent with following an exact one-to-one relation, as expected if both Hβ and MgII are emitted at the same radius from the central ionizing source. The resulting virial black hole mass estimator based on rest-frame UV observables is shown to reproduce black hole mass measurements based on reverberation mapping to within a factor of 2.5 (1σ). Finally, the new UV black hole mass estimator is shown to produce identical results to the established optical (Hβ) estimator when applied to 128 intermediate-redshift (0.3 <z <0.9) quasars drawn from the Large Bright Quasar Survey and the radio-selected Molonglo quasar sample. We therefore conclude that the new UV virial black hole mass estimator can be reliably used to estimate the black hole masses of quasars from z~ 0.25 through to the peak epoch of quasar activity at z~ 2.5 via optical spectroscopy alone.