I report on the connections between the so-called carbon-enhanced metal-poor (CEMP) stars and nucleosynthesis by the first generations of stars in the Universe. In a nutshell, a plausible story can now be told establishing that a subset of the CEMP stars exhibit the nucleosynthetic signature of the VERY first stars, providing tools for understanding the nature of these stars, born within a few hundred million years after the Big Bang. In addition, I comment on a possible resolution of the discrepancy between the abundance of Li on the Spite Plateau and the primordial value of Li expected from Big Bang Nucleosynthesis, which is also revealed by analysis of the CEMP stars. Current and future observations with Gemini and other telescopes, and perspectives on other required future studies are presented.