Quantum nonlocality is arguably among the most counter-intuitive phenomena predicted by quantum theory. In recent years, the development of an abstract theory of nonlocality has brought a much deeper understanding of the subject. In parallel, experimental progress allowed for the demonstration of quantum nonlocality in a wide range of physical systems, and brings us close to a final loophole-free Bell test. Here we combine these theoretical and experimental developments in order to explore the limits of quantum nonlocality. This approach represents a thorough test of quantum theory, and could provide evidence of new physics beyond the quantum model. Using a versatile and high-fidelity source of pairs of polarization entangled photons, we explore the boundary of quantum correlations, present the most nonlocal correlations ever reported, demonstrate the phenomenon of more nonlocality with less entanglement, and show that non-planar (and hence complex) qubit measurements can be necessary to reproduce the strong qubit correlations that we observed. Our results are in remarkable agreement with quantum predictions.