Let me give a brief overview of those pre-IE languages in Europe of which we know that they were (and still are) there.
1. Languages that are still spoken
The obvious one is of course Basque in the western Pyrenees. Basque is SOV, ergative and agglutinating, and shows no shred of evidence for a relationship to any other living language.
In the southeastern corner of Europe, on the boundary to Asia, we have the Caucasian languages, which fall into three different families not known to be related to each other or to anything else. While most of them are SOV, ergative and somewhere between agglutinating and fusional, and all of them have large phoneme inventories with uvulars and ejectives, the three families are very different from each other.
2. Fragmentarily attested languages
In the west, we have Iberian in a strip about 100 km deep along the Spanish Mediterranean coast, written in a script (with a northern and a southern variant) of whose letters we roughly know the sound values, but the language is not understood. Basque is not helpful here, the languages do not seem to be particularly close.
Another language written in a similar script is Tartessian, in southwestern Spain and southern Portugal, also not understood. The celtologist John T. Koch has proposed a reading of the Tartessian inscriptions as a Celtic language, which fits the fact that many place names in the area are Celtic, but this is controversial.
The best-known of the fragmentary non-IE languages of Europe surely is Etruscan in Italy. The script can be read with few problems, but the language is poorly understood and unclassified, except that Rhaetic in the Italian Alps and Lemnian in the Aegean appear to be related, but these two are even less known.
On Crete, we have two undeciphered scripts (not counting the enigmatic Phaistos Disc), Minoan hieroglyphs and Linear A, and some inscriptions in Greek letters but an unknown language designated Eteocretan. The situation on Cyprus is similar, with an undeciphered Cypro-Minoan script and an unknown language recorded in the (readable) Cypro-Syllabic script, Eteocypriot.
Europe north of the Alps is almost completely blank, as the art of writing arrived here only after the Indo-Europeanization and Uralicization was complete - the sole exception being Pictish, the unknown language of a few Ogham inscriptions in northeastern Scotland, which may be a non-Indo-European language or just an aberrant form of Celtic.
The landscape of Europe is laced with place names of unknown origin. Many of them, especially river names, seem to form a vast fairly homogenous network of recurring names, the Old European hydronymy. The German scholar Hans Krahe attributed them to Indo-European; Theo Vennemann assumes that they are Vasconic, i.e. from languages related to Basque. Both hypotheses are controversial.
Most European languages have many words with unknown etymologies. In Greek, these make about a third of the vocabulary, and are often attributed to an unknown language called Pelasgian. The situation in Germanic and Celtic is not much different. The Insular Celtic languages also have undergone a thorough restructuring of their syntax. This is sometimes attributed to a substratum language, which some scholars assume to be related to Semitic, but most scholars reject that relationship.
...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