Key item: The Basques really are that distinct and separate. Even with modern genetic techniques and some adventurous linguists it is hard to connect them to anyone very solidly. But at least there have been some new and interesting developments.
The Basque language, Euskara, is believed to be an isolate. It is also isolated within itself, with five dialects, some mutually unintelligible. The Basque people have been isolates for centuries as well, retreating into the hills to avoid domination by Franks and Visigoths, then both the Roman and Muslim empires. DNA evidence shows two narrowings between the 11th and 16th C. The second most likely coincides with the reign of Ferdinand and Isabella. These only show in the genetic results of the "peri-Basque" area. There was some mixing there. The central Basque regions have no mixing. For this reason, they are treated as a base population of what the genetics of Europe were like before the Celts and then Germanic tribes arrived. Yes, they seem to be that unmixed. No traces of those later Indo-Europeans. The Sardinians of the interior are treated similarly by geneticists. In both cases it is considered possible that a much earlier Indo-European population, possibly Illyrian-Albanian, was present in Europe as well. Maybe. Not much evidence they were connected to the Basques, though.
Those stories you may have seen in the last few years about the Irish Not Being Celts! are from this. It's a fun headline, but it only means there were people there before the Celts, and they weren't completely erased by the invaders.
Various theories have popped up over the years speculating what languages Euskara might be related to, but none have been much convincing to linguists. It is clearly not related to the Indo-European and Semitic languages of the people they have lived near, and thus some version of it was in place when those peoples settled/invaded/colonised in the 2nd Millenium BCE. That would make the languages of the first spread of agriculture from the Fertile Crescent slowly outward the most likely. The people who built Stonehenge, for example, did not speak the languages of the Celts who later came in and took the place over. It is all pre-writing, so we don't know what they spoke in Europe. It is also possible that Basque predates even the spread of agriculture, as their area was one of the few refugia in europe during the last Ice Age. Thus those languages might have come from a few families, including ones that have no descendants. Other examples of these would be Etruscan and Proto-Sardinian. That Proto-Basque might be related to Proto-Sardinian is given some credibility even by fussier linguists.
One far-fetched sounding theory has been that it is part of the Dene-Caucasian family, which would connect it to languages in the North Caucasus, the Yeniseian languages of Siberia, and ultimately to some Native American languages from the second migration into North America, including Athabaskan, Tlingit, Hopi and Navaho. Far-fetched, yes, and not well accepted among linguists, but the pieces may be coming together on it bit by bit. Over a decade ago linguist Edward Vajda put forth evidence that the Na-Dene languages were related to Ket, a Yeneseian language. So that would be one step. There is more recent evidence that Basque shares structural similarities with Northeastern Caucasian languages, especially Chechen, so that would be a second link. There is enormous variety in the Caucasus. Whether there is genetic connection is not known. And the Chechen to Ket connection has not been made, either.
It's one of those theories I hope proves out, but it's a long way from solid at this point. Spain to Arizona the long way is quite a trek.