Let me try a preliminary overview of what may have happened linguistically in prehistoric Europe. Nothing of what follows can be considered certain, of course; all of this is just material for discussion, and may be falsified by things I do not know yet. Comments and critiques are welcome.
0. It is unknown when the first languages were spoken in Europe, depending on to which degree Homo heidelbergensis or Homo neanderthalensis had language (they probably did have some kind of language, but perhaps less sophisticated than ours). Most likely, these languages were wiped out after the arrival of Homo sapiens, when their speakers died out. There is only a remote possibility that some words pertaining to European nature and wildlife were borrowed by Homo sapiens.
1. For our purposes, then, the linguistic prehistory of Europe began with the arrival of Homo sapiens in the Upper Paleolithic, c. 45,000 BC. Homo sapiens came from the east, on two routes, one along the Mediterranean coast, one north of the Black Sea and the Alps. So we get two great families, let's call them Paleo-Mediterranean and Paleo-Transalpine, which may in turn have been branches of a single large family rooted in the Near East, but could just as well have been utterly different.
2. During the Upper Paleolithic, Paleo-Mediterranean diversifies more and more; perhaps, later immigrations from the Near East or North Africa, add even more languages. Paleo-Transalpine also diversifies, but as the climate worsens, most of Europe north of the Alps is more and more depopulated, and most branches of Paleo-Transalpine vanish.
3. At the Last Glacial Maximum, ca. 20,000 to 16,000 BC, only two branches of Paleo-Transalpine are left, one in southern France, and one north of the Black Sea; we may call them Paleo-Atlantic and Paleo-Pontic, respectively. These two may have descendants even today, namely Basque of Paleo-Atlantic, and Abkhaz-Adyghean (Northwest Causasian) and Nakh-Daghestanina (Northeast Caucasian) of Paleo-Pontic. (Alternatively, these could be Mediterranean languages that went north in the Mesolithic, see point 5.) Of course, after all those millennia after separation, these are now utterly different language families, to the point that a time-travelling linguist would no longer be able to find clear evidence of relationship. Meanwhile, Mediterranean Europe holds perhaps up to a dozen different families, their common descent from Paleo-Mediterranean no longer discernible.
4. After the Glacial Maximum, Europe north of the Alps is gradually repopulated by Paleo-Atlantic and Paleo-Pontic speakers. It is hard to say where they meet, but probably somewhere in Central Europe. Meanwhile, linguistic diversity in Mediterranean Europe remains quite high, at 5 to 10 families that would be discernible to a time-travelling linguist.
5. The ice age ends about 9600 BC, and Europe enters the Mesolithic. Paleo-Atlantic speakers settle in the British Isles (then not yet islands) and in western Scandinavia, while Paleo-Pontic speakers settle around the Baltic Sea. Some Mediterranean groups probably venture northwards; maybe Basque and one or both of the North Caucasian families are carried northward by them, if they are not survivors of Paleo-Atlantic and Paleo-Pontic, respectively. Meanwhile, another family, Mitian spreads from a centre in Central Asia, and reaches the easternmost recesses of Europe.
6. The European Neolithic begins about 7000 BC, with the arrival of the first European farmers from Anatolia. In the following 2000 years, a demic expansion of agriculture into the Balkan Peninsula, Central Europe and the Mediterranean coasts takes place. This results in the spread of two large Neolithic language families, one north, one south of the Alps. We could call these Danubian and Cardial-Impresso, respectively. The Iberian language of pre-Roman eastern Spain could be a part of the Cardial-Impresso family. These two families could be branches of one larger unit, but this is uncertain. The westernmost branch of Mitian diversifies in the Pontic-Caspian steppe, giving birth to Macro-Indo-European and Macro-Uralic.
7. Around 4500 BC, the first "Kurgan wave" of Macro-Indo-European speakers spreads westward through the Lower Danube region into Central Europe, eclipsing most of the Danubian family. Their language becomes Aquan, the language of the Old European Hydronymy. At about the same time, Macro-Uralic spreads across northeastern Europe in the framework of the Pit-Comb Ware culture.
8. Around 3500 BC, the second "Kurgan wave" carries Proto-Anatolian to the eastern parts of the Balkan Peninsula, from whence it later enters Anatolia.
9. Around 3000 BC, the third "Kurgan wave" spreads Indo-European languages into the Balkan Peninsula and Central Europe, and also eastward into Central Asia. Aquan speakers are pushed westward into France, the British Isles, the Iberian Peninsula and northern Italy. At the same time, Uralic proper spreads in the northeast, eclipsing the other Macro-Uralic languages.
10. In the Bronze Age, Indo-European and Uralic displace most other European languages. The Aquan family perhaps holds out longest in the British Isles, where it may become the language of a civilization that underlies the Celtic and Germanic traditions of Elves, the Greek traditions of Hyperborea and the Homeric Phaeacians, and perhaps Plato's Atlantis. The Germanic nautic terminology may be from this language, and it may have exerted a substratum influence on Insular Celtic. Alas, no clear archaeological evidence of such a civilization has been found yet. Basque holds out in southwestern France and the western Pyrenees, Iberian in the east and Tartassian in the southwest of the Iberian Peninsula. Etruscan seems to be a younger stratum than Aquan in Italy; it perhaps arrived from northwestern Anatolia around 1200 BC (the Roman foundation myth may actually relate the arrival of the Etruscans (pre-republican Rome was ruled by an Etruscan nobility) from Troy). There are also non-IE languages on Crete (Minoan, Eteocretan) and Cyprus (Cypro-Minoan, Eteocypriot). In the Caucasus, we have the three Caucasian families. The rest is (literally!) history.
...brought to you by the Weeping Elf
Tha cvastam émi cvastam santham amal phelsa. -- Friedrich Schiller
ESTAR-3SG:P human-OBJ only human-OBJ true-OBJ REL-LOC play-3SG:A