The study of the long-dead early generations of massive stars is crucial in order to obtain a complete picture of the chemical evolution of the Universe, hence the origin of the elements. The nature of these stars can be inferred indirectly by investigating the origin of low-mass metal-poor stars observed in our Galaxy, some of which are almost as old as the Universe. The peculiar extremely iron-poor Carbon-Enhanced Metal-Poor (CEMP) stars, whose precise origin is still debated, are thought to have formed with the material ejected by only one or very few previous massive stars. The main aim of this thesis is to explore the physics and the nucleosynthesis of the early generations of massive stars. It is achieved by combining stellar evolution modeling including rotation and full nucleosynthesis with observations of CEMP stars.