Context. The most metal-poor stars in the Milky Way witnessed the early phases of formation of the Galaxy, and have chemical compositions that are close to the pristine mixture from Big Bang nucleosynthesis, polluted by one or few supernovae. Aims: Only two dozen stars with ([Fe/H] < -4) are known, and they show a wide range of abundance patterns. It is therefore important to enlarge this sample. We present the first results of an effort to identify new extremely metal-poor stars in the Milky Way halo. Methods: Our targets have been selected from low-resolution spectra obtained as part of the Sloan Digital Sky Survey, and followed-up with medium resolution spectroscopy on the 4.2 m William Herschel Telescope and, in a few cases, at high resolution on the 9.2 m Hobby-Eberly Telescope. Stellar parameters and the abundances of magnesium, calcium, iron, and strontium have been inferred from the spectra using classical model atmospheres. We have also derived carbon abundances from the G band. Results: We find consistency between the metallicities estimated from SDSS and those from new data at the level of 0.3 dex. The analysis of medium resolution data obtained with ISIS on the WHT allows us to refine the metallicities and in some cases measure other elemental abundances. Our sample contains 11 new metal-poor stars with [Fe/H] < -3.0, one of them with an estimated metallicity of [Fe/H] ~ -4.0. We also discuss metallicity discrepancies of some stars in common with previous works in the literature. Only one of these stars is found to be C-enhanced at about [C/Fe] ~ + 1, whereas the other metal-poor stars show C abundances at the level of [C/Fe] ~ + 0.45. Based on observations obtained with the Hobby-Eberly Telescope, which is a joint project of the University of Texas at Austin, the Pennsylvania State University, Stanford University, Ludwig-Maximilians-Universität München, and Georg-August-Universität Göttingen.The reduced spectra as FITS files are only available at the CDS via anonymous ftp to http://cdsarc.u-strasbg.fr (http://130.79.128.5) or via http://cdsarc.u-strasbg.fr/viz-bin/qcat?J/A+A/593/A10