Can relativity be considered complete ? From Newtonian nonlocality to quantum nonlocality and beyond

We review the long history of nonlocality in physics with special emphasis on the conceptual breakthroughs over the last few years. For the first time it is possible to study "nonlocality without signaling" {\it from the outside}, that is without all the quantum physics Hilbert space artillery. We emphasize that physics has always given a nonlocal description of Nature, except during a short 10 years gap. We note that the very concept of "nonlocality without signaling" is totally foreign to the spirit of relativity, the only strictly local theory.