The Celtic languages were spread in a vast area of western and central Europe. There's no doubt that these regions, had been settled by humans for many millennia before any speakers of Celtic languages could have arrived there. With exception to few known languages (e.g Basque, Rhaetic), there is no attested documentation of these pre-Celtic languages. Some scholars have attempted to identify evidence for their survival into the first millennium CE via the examination of lexical items which bear phonological features which, they argue, cannot be Celtic, in fact not even Indo-European.
In the beginning of the 20th century, Morris Jones was the first to focus on a number of syntactic
parallels between Welsh and Egyptian (also Berber to some extent). He did not propose that an Afro-Asiatic substratum was necessary to explain the insular Celtic features, but he did raise the question. Many followed this idea for several decades, including Hewitt (2009) who listed 39 features which have been proposed as diagnostic of contact between proto-insular Celtic and a language of Afro-Asiatic type. In 1949, Julius Pokorny saw parallels not only from Afro-Asiatic languages, but also from Bantu, Basque, Caucasian, Finno-Ugric, and Eskimo-Aleut. Heinrich Wagner (1959) followed Pokornys steps, but focused mainly on the verbal system which is of Afro-Asiatic typology, but not necessarily Afro-Asiatic genetically. It would be wise to keep Wagner's conclusion in mind.
In general the Afro-Asiatic substratum theory, although enjoying some popularity, has never found much favor with scholars of the Celtic languages. Graham Isaac (2007) for instance was very critical and attacked this substratum theory. He noted, just like Hewitt, that many of the proposed parallels with Afro-Asiatic are common cross-linguistically. T. A. Mikhailova (2007) calls those theories (including Basque, Uralic, Altaic, Kartvelian, Hamito-Semitic etc) "fantastic speculations" and that the problem itself has become a perpetuum mobile of Celtic and Germanic studies. Of course, Basque cannot be denied as a substratum in continental Celtic, but we cannot speak of Basque substratum wherever Celtic was spoken.
Many of these theories focus mainly on insular Celtic. The number of languages that were spoken in the continental region is unknown. The same is true for the British isles. Whenever the Celtic speakers arrived there, they were probably not numerous (in comparison to the local population) — there is hardly any archaeological evidence for large-scale migrations into Britain or Ireland in the Bronze Age. Most probably there were many substratum languages when the Celts entered the British isles, and the languages of those Celts were already differentiated by that time. The same can be seen in the Italian penisnsula, where Picene and Etruscan were unrelated to each other. Then we have the migrations of the early farmers into Europe. They in turn must have been speaking a language totally different from any of the aforementioned language groups of this article (a language related to Hattic, to Urartian or another unknown language?) and possibly made some contribution to the development of Celtic in the central European regions.
So, what is the deal with pre-Celtic? We do not attempt to reach a conclusion on this article, other than the substrata influence on Celtic may have had numerous sources.
Hildegard L.C. Tristram (ed.), ʻThe Celtic Languages in Contactʼ, 2007 Potsdam University Press
S. Hewitt, ʻRemarks on the Insular Celtic / Hamito-Semitic questionʼ, 2009 Blackwell Publishing Ltd
R. Matasović, ʻThe substratum in Insular Celticʼ, 2012 Journal of Language Relationship
J.F Eska, ʻContact and the Celtic Languagesʼ in "The Handbook of Language Contact", 2010 Willey - Blackwell