The first stars in the Universe are predicted to have been much more massive than the Sun. Gravitational condensation, accompanied by cooling of the primordial gas via molecular hydrogen, yields a minimum fragmentation scale of a few hundred solar masses. Numerical simulations indicate that once a gas clump acquires this mass it undergoes a slow, quasi-hydrostatic contraction without further fragmentation; lower-mass stars cannot form. Here we show that as soon as the primordial gas--left over from the Big Bang--is enriched by elements ejected from supernovae to a carbon or oxygen abundance as small as approximately 0.01-0.1 per cent of that found in the Sun, cooling by singly ionized carbon or neutral oxygen can lead to the formation of low-mass stars by allowing cloud fragmentation to smaller clumps. This mechanism naturally accommodates the recent discovery of solar-mass stars with unusually low iron abundances (10(-5.3) solar) but with relatively high (10(-1.3) solar) carbon abundance. The critical abundances that we derive can be used to identify those metal-poor stars in our Galaxy with elemental patterns imprinted by the first supernovae. We also find that the minimum stellar mass at early epochs is partially regulated by the temperature of the cosmic microwave background.