Metal-poor stars trace the earliest phases in the chemical enrichment of the Universe. They give clues about the early assembly of the Galaxy as well as on the nature of the first stellar generations. Multi-object spectroscopic surveys play a key role in finding these fossil records in large volumes. Here we present a novel analysis of the metal-poor star sample in the complete Radial Velocity Experiment (RAVE) Data Release 5 catalog with the goal of identifying and characterizing all very metal-poor stars observed by the survey. Using a three-stage method, we first identified the candidate stars using only their spectra as input information. We employed an algorithm called t-SNE to construct a low-dimensional projection of the spectrum space and isolate the region containing metal-poor stars. Following this step, we measured the equivalent widths of the near-infrared Ca ii triplet lines with a method based on flexible Gaussian processes to model the correlated noise present in the spectra. In the last step, we constructed a calibration relation that converts the measured equivalent widths and the color information coming from the 2MASS and WISE surveys into metallicity and temperature estimates. We identified 877 stars with at least a 50% probability of being very metal-poor ([Fe=H] < 2 dex), out of which 43 are likely extremely metal-poor ([Fe=H] < 3 dex). The comparison of the derived values to a small subsample of stars with literature metallicity values shows that our method works reliably and correctly estimates the uncertainties, which typically have values [Fe=H] 0:2 dex. In addition, when compared to the metallicity results derived using the RAVE DR5 pipeline, it is evident that we achieve better accuracy than the pipeline and therefore more reliably evaluate the very metal-poor subsample. Based on the repeated observations of the same stars, our method gives very consistent results. We intend to study the identified sample further by acquiring high-resolution spectroscopic follow-up observations. The method used in this work can also easily be extended to other large-scale data sets, including to the data from the Gaia mission and the upcoming 4MOST survey.