The early Universe had a chemical composition consisting of hydrogen, helium and traces of lithium(1); almost all other elements were subsequently created in stars and supernovae. The mass fraction of elements more massive than helium, Z, is known as 'metallicity'. A number of very metal-poor stars has been found(2,3), some of which have a low iron abundance but are rich in carbon, nitrogen and oxygen(4-6). For theoretical reasons(7,8) and because of an observed absence of stars with Z<1.5x10(-5), it has been suggested that low-mass stars cannot form from the primitive interstellar medium until it has been enriched above a critical value of Z, estimated to lie in the range 1.5x10(-8) to 1.5x10(-6) (ref. 8), although competing theories claiming the contrary do exist(9). (We use 'low-mass' here to mean a stellar mass of less than 0.8 solar masses, the stars that survive to the present day.) Here we report the chemical composition of a star in the Galactic halo with a very low Z (<= 6.9x10(-7), which is 4.5x10(-5) times that of the Sun(10)) and a chemical pattern typical of classical extremely metal-poor stars(2,3)-that is, without enrichment of carbon, nitrogen and oxygen. This shows that low-mass stars can be formed at very low metallicity, that is, below the critical value of Z. Lithium is not detected, suggesting a low-metallicity extension of the previously observed trend in lithium depletion(11). Such lithium depletion implies that the stellar material must have experienced temperatures above two million kelvin in its history, given that this is necessary to destroy lithium.