In the framework of the ESO Large Programme "First Stars", very high-quality spectra of some 70 very metal-poor dwarfs and giants were obtained with the ESO VLT and UVES spectrograph. These stars are likely to have descended from the first generation(s) of stars formed after the Big Bang, and their detailed composition provides constraints on issues such as the nature of the first supernovae, the efficiency of mixing processes in the early Galaxy, the formation and evolution of the halo of the Galaxy, and the possible sources of reionization of the Universe. This paper presents the abundance analysis of an homogeneous sample of 35 giants selected from the HK survey of Beers et al. (1992, Cat. <J/AJ/103/1987>, 1999, Cat. <J/AJ/117/981>), emphasizing stars of extremely low metallicity: 30 of our 35 stars are in the range -4.1<[Fe/H]<-2.7, and 22 stars have [Fe/H]<-3.0. Our new VLT/UVES spectra, at a resolving power of R~45000 and with signal-to-noise ratios of 100-200 per pixel over the wavelength range 330-1000 nm, are greatly superior to those of the classic studies of McWilliam et al. (1995AJ....109.2757M) and Ryan et al. (1996ApJ...471..254R).