In the last decades, luminous accreting super-massive black holes have been discovered within the first Gyr after the Big Bang, but their origin is still an unsolved mystery. We discuss our state-of-the-art theoretical knowledge of their formation physics and early growth, and describe the results of dedicated observational campaigns in the X-ray band. We also provide an overview of how these systems can be used to derive cosmological parameters. Finally, we point out some open issues, in light of future electro-magnetic and gravitational-wave astronomical facilities.