Gravity's unique geometric structure is manifest in strong field regions, especially around black holes. The new-born era of gravitational-wave astronomy and of very long baseline interferometry is now providing data from such regions, carrying information about the gravitational interaction in highly dynamical setups. The access to this new and uncharted territory may hold the key to outstanding puzzles, such as the nature of dark matter, or the fate of singularities or horizons within a quantum field theory context. The breakthroughs at the observational and experimental level make strong gravity physics one of this century's most active and exciting fields of research. I propose to explore the discovery potential of black holes, a foundational project which will transform the field into data-driven with solid theoretical foundations. This coordinated program will study and test the strong-field regime of gravity and the matter content of our universe. The project will explore comprehensively the potential of black holes and compact binaries to perform spectroscopy and to strengthen the black hole paradigm. I will ascertain the evidence for black holes, providing new and robust tools to quantify their existence with electromagnetic and gravitational-wave observations. Finally, I will undertake a systematic study of environmental effects, including the ability for new observations to study the host galaxy, and will constrain the existence of new fundamental ultralight fields in our universe to unprecedented levels. The project aims to implement pipelines for its realization in planned and ongoing missions. The proposed program will significantly advance our knowledge of Einstein's field equations and their role in foundational questions, as well as the interplay with high energy, astro and particle physics. This is a multidisciplinary program with an impact on our understanding of gravity at all scales.