Very metal-poor stars are of obvious importance for many problems in chemical evolution, star formation, and galaxy evolution. Finding complete samples of such stars which are also bright enough to allow high-precision individual analyses is of considerable interest. We demonstrate here that stars with iron abundances [Fe/H] < -2 dex, and down to below -4 dex, can be efficiently identified within the Radial Velocity Experiment (RAVE) survey of bright stars, without requiring additional confirmatory observations. We determine a calibration of the equivalent width of the calcium triplet lines measured from the RAVE spectra onto true [Fe/H], using high spectral resolution data for a subset of the stars. These RAVE iron abundances are accurate enough to obviate the need for confirmatory higher-resolution spectroscopy. Our initial study has identified 631 stars with [Fe/H] ≤ -2, from a RAVE database containing approximately 200,000 stars. This RAVE-based sample is complete for stars with [Fe/H] ≲ -2.5, allowing statistical sample analysis. We identify three stars with [Fe/H] ≲ -4. Of these, one was already known to be "ultra metal-poor," one is a known carbon-enhanced metal-poor star, but we obtain [Fe/H] = -4.0, rather than the published [Fe/H] = -3.3, and derive [C/Fe] = +0.9, and [N/Fe] = +3.2, and the third is at the limit of our signal-to-noise ratio. RAVE observations are ongoing and should prove to be a rich source of bright, easily studied, very metal-poor stars.