Tracing the origins of the Phoenicians from their historically well documented peak (well documented in part, because it takes place after they invented the alphabet), to their deeper origins in the city of Byblos which is one of the oldest cities in the world, fills an important piece of that puzzle.
It suggests one route that Mesopotamiam myth could have worked its way into Semitic culture (although I gloss over later Iron Age contacts that could also have been a source) and illustrates the intimate degree to which the Phoenician culture and Egyptian cultures were intertwined for thousands of years. A robust maritime trade based Phoenician culture thousands of years older than is usually assumed suggests connections throughout the region that might not otherwise make sense and coincides with similarly sophisticated Sumerian maritime trade via the Persian Gulf and beyond.
Early Phoenician Society And Its Neighbors
Historically, the focus on Phoenician society has been on its iron age heyday. But, the modern trend is to see their culture as one that is in continuity with the earliest Neolithic cultures of the Fertile Crescent. Phoenicians may have very deep roots in the Levant and probably traded with the Sumerians, the pre-Bronze Age collapse Minoans in Crete, the pre-Greek people of the Greek mainland, the later Myceneans Greeks, and the Ancient Egyptians who were a dominant trading partner in the early Phoenician period.
A lecture from 2008 makes the case that Phoenician society was distinct from neighboring Semitic peoples, much earlier, successfully defending land based Amorite invasions ca. 2200 BCE to 2000 BCE, with the only Semitic maritime society.
This coincides with the period immediately following the linguistically Semitic Akkadian Empire that encompassed essentially all of the previously Sumerian Mesopotamia (a non-Afro-Asiatic, non-Indo-European population linguistically who seem to show cultural continuity back to 5300 BCE or earlier). The Akkadian empire mounted military campaigns against the nearby inland city of Ebla, but never managed to extend its reach as far as coastal cities like Byblos, Sidon or Tyre. "After the fall of the Akkadian Empire, the Akkadian peoples of Mesopotamia eventually coalesced into two major Akkadian speaking nations; Assyria in the north, and a few centuries later, Babylonia in the south."
Pre-Akkadian Sumerians had trade networks that included "obsidian from far-away locations in Anatolia and lapis lazuli from Badakhshan in northeastern Afghanistan, beads from Dilmun (modern Bahrain), and several seals inscribed with the Indus Valley script suggest a remarkably wide-ranging network of ancient trade centered around the Persian Gulf [to Pakistan] . . . cedar from Lebanon [which was the Phoenician homeland and] . . . resin in the tomb of Queen Puabi at Ur, indicates it was traded from as far away as Mozambique."
Significant components of the Hebrew Bible books of Genesis and Exodus have clear antecedents in Sumerian legends that were absorbed by the Akkadians, and the Sumerian language (which was the earliest written language) survived as a liturgical, literary and scientific language until the 1st century CE, about two thousand years after it ceased to be a living language of ordinary people.
The lecturer argues that cultures in continuity with the Phoenicians are present at least as far back as 3200 BCE when shipped lumber from Byblos (in modern Lebanon) to the ancient Egyptians and had statutes to "Baalat Gebal—Our Lady of Byblos."
Watson Mills and Roger Bullard suggest that during the Old Kingdom [2686 BC – 2181 BC], Byblos was virtually an Egyptian colony. The growing city was evidently a wealthy one and seems to have been an ally (among "those who are on his waters") of Egypt for many centuries. First Dynasty tombs [ca. 3100 BCE] used timbers from Byblos. One of the oldest Egyptian words for an ocean going boat was "Byblos ship". Archaeologists have recovered Egyptian-made artifacts as old as a vessel fragment bearing the name of the Second dynasty ruler Khasekhemwy, although this "may easily have reached Byblos through trade and/or at a later period.". Objects have been found at Byblos naming the 13th dynasty Egyptian king Neferhotep I, and the rulers of Byblos maintained close relationships with the New Kingdom pharaohs of Ancient Egypt. Around 1350 BC, the Amarna tablets include 60 letters from Rib-Hadda and his successor Ili-Rapih who were rulers of Byblos, writing to the Egyptian government. This is mainly due to Rib-Hadda's constant pleas for military assistance from Akhenaten. They also deal with the conquest of neighboring city-states by the Hapiru.
It appears Egyptian contact peaked during the 19th dynasty [ca 1292 to 1187 BCE], only to decline during the 20th and 21st dynasties. Although the archaeological evidence seems to indicate a brief resurgence during the 22nd and 23rd dynasties, it is clear after the Third Intermediate Period [1070 BCE to 664 BC] the Egyptians started favoring Tyre and Sidon instead of Byblos.
Archaeological evidence at Byblos, dating back to around 1200 BC, shows existence of a Phoenician alphabetic script of twenty-two characters; an important example of this script is the sarcophagus of king Ahiram. The use of the alphabet was spread by Phoenician merchants through their maritime trade into parts of North Africa and Europe.Notably, in the First Dynasty, Egyptian royal funerals included not only the cedars of Lebanon, but the human sacrifice of hundreds of retainers to assist the deceased Pharohs in the afterlife.
Tyre and Sidon are described as colonies of Byblos each founded about 2750 BCE, with more distant colonies coming later, perhaps after Bronze Age collapse ca. 1200 BCE. The author of the lecture argues that the archaeological evidence shows that these cities (presumably because of their maritime prowess) were spared the invasions of the Sea Peoples seen in the rest of the Eastern Mediterranean.
Prior archaeological cultures around Byblos could have been in continuity with the Phoenicians even as early as 4500 BCE when the earliest ships similar to theirs appeared, or as early as 6000 BCE when villages began to spring up in the Byblos region not long after the end of the pre-pottery Neolithic era in the Fertile Crescent around 6200 BCE.
The Neolithic 3 (PN) began around 6,400 BC in the Fertile Crescent. By then distinctive cultures emerged, with pottery like the Halafian (Turkey, Syria, Northern Mesopotamia) and Ubaid (Southern Mesopotamia). This period has been further divided into PNA (Pottery Neolithic A) and PNB (Pottery Neolithic B) at some sites. The Chalcolithic period began about 4500 BC, then the Bronze Age began about 3500 BC, replacing the Neolithic cultures.Byblos may even date back as far as the Pre-Pottery Neolithic A era just a few hundred years after Jericho.
Byblos and later Phoenician city-states may have had trade relationships with Sumeria for its entire existence until it was supplanted by Eastern Semitic Akkadians, who probably originated in the Northern Levant and are the most basal division in the phylogeny of known Semitic languages.
There is no clear indication, however that Semitic peoples ever made in North of Cyrpus or Syria, for example, into the Aegean or Anatolia, except as traders, although this region doesn't enter written history until sometime around 2000 BCE. The Indo-European Hittite Empire (ca. 1833 BCE to 1178 BCE preceded an arrival in the region from the North of Indo-European people ca. 2000 BCE to 1900 BCE) came to rule all of Anatolia and much of the Northern Levant. Their predecessors spoke languages that were neither Indo-European nor Semitic such as Hattic and Hurrian, both possibly related to the modern Caucuasian langauges, from some time prior to the Akkadian Empire's appearance to the South. Neolithic settlements appear in Anatolia by at least 7500 BCE, at least some of which have been continuously inhabited since 6300 BCE or earlier and is home to stone structures that may date to the Mesolithic era immediately preceding the Neolithic revolution in the Fertile Crescent (ca. 9000 BCE).
The Phoenicians whose core cities of Byblos, Sidon and Tyre were just beyond the furthest point of Hittite influence at its peak, and were in a Egyptian sphere of influence in the Hittite era. The early Phoenicians probably traded with the the pre-Greek Helladic peoples of modern day Greece, the non-Indo-European Minoans in Crete, the Indo-European Mycenean Greeks and Anatolian Trojans, the pre-Hittite non-Indo-European Hattic people of Anatolia, and the later Hittite people of Anatolia.
The origin of the Semitic languages themselves within the Afro-Asiatic language family is not clearly resolved. Geographically, it neighbors the ancient Egyptian Coptic language family, and it is known that the Ethiosemitic languages were a relatively late (probably Bronze Age) offshoot of the South Semitic languages of places like Yemen prior to the adoption of Arabic. But, the debate over whether the Afro-Asiatic languages all derive from Semitic langauges, or the Semitic languages derive from Coptic, is unresolved although the modern trend is to favor an African origin for the Semitic languages. The Halaf culture ca. 6100 to 5400 BCE in roughly the area of modern day inland Syria is the first point at which there is a strong cultural contrast within the Fertile Crescent with Mesopotamia where a Sumerian or pre-Sumerian culture call the Ubaid culture was emerging. The Halaf culture could be the archaeological culture most reliably seen as a point of origin for a proto-Central Semitic language, or could be a cultural dead end, driven to extinction by the expansion of the Ubaid culture from Southern Mesopotamia.
Byblos was founded several thousand years after Jericho to the South in the Levant (founded ca. 9600 BCE) although this may overstate the matter as there appears to have been some settlement in Byblos much earlier. Jericho is the oldest known city in the Levant and in the world. Jericho was relocated to a new site nearby ca. 6800 BCE with many layers of cities between then and it abandonment. Jericho was a Semitic city by the Middle Bronze Age ca. 1700 BCE, but it isn't at all clear what kind of linguistic affinities different regions might have had before the Bronze Age. Jericho was abadoned from around 1600 BCE to 800 BCE during an era when Phoenica was thriving. A Semitic language appearance ca. 6800 BCE when Jericho is re-established that spreads to Byblos ca. 6000 BCE, is also a plausible scenario. An out of Egypt origin for Semitic also suggests 3600 BCE when this civilization starts a period of rapid expansion as a plausible era to consider.
Ancient DNA suggests that the Phoenicians had local origins in the North Levant going back thousands of years to the Mesolithic era, rather than being migrants from the Persian Gulf or Red Sea as Herodotus' account in his History, written c. 440 BCE claims based upon Persian sources, although his account would have seemed plausible at the time, because Mesopotamia and the Southern Levant and Northern Ethiopia all would have been linguistically Semitic then or within the last few centuries at the time his History was written.
The Neolithic revolution arrived in Andalusia (basically the Southern tip of Spain) with Fertile Crescent crops arrive a few centuries before the main Southern European Cardium Pottery Neolithic culture reaches Iberia.
In the 6th millennium BC, Andalusia experiences the arrival of the first agriculturalists. Their origin is uncertain (though North Africa is a serious candidate) but they arrive with already developed crops (cereals and legumes). The presence of domestic animals instead is unlikely, as only pig and rabbit remains have been found and these could belong to wild animals. They also consumed large amounts of olives but it's uncertain too whether this tree was cultivated or merely harvested in its wild form. Their typical artifact is the La Almagra style pottery, quite variegated.
The Andalusian Neolithic also influenced other areas, notably Southern Portugal, where, soon after the arrival of agriculture, the first dolmen tombs begin to be built c. 4800 BC, being possibly the oldest of their kind anywhere.
C. 4700 BC Cardium Pottery Neolithic culture (also known as Mediterranean Neolithic) arrives to Eastern Iberia. While some remains of this culture have been found as far west as Portugal, its distribution is basically Mediterranean (Catalonia, Valencian region, Ebro valley, Balearic islands).
The interior and the northern coastal areas remain largely marginal in this process of spread of agriculture. In most cases it would only arrive in a very late phase or even already in the Chalcolithic age, together with Megalithism.This earliest wave of farming in the area that would be home to later Megalithic cultures, Bell Beaker cultures, and Celtic expansion. The same area is a destination point for Phoenician, Roman, Vandal and Moorish migrants.
The Andalusian Neolithic is notable for a dearth of cattle relative to the Cardial Pottery Neolithic that later on Spain's eastern shores, probably from a source in the Northern Levant in the vicinity of modern Syria and the Phoenician homeland, although Cardial Pottery Neolithic ancient DNA is quite similar to that of the LBK Neolithic in Central Europe and more like modern West Asia than like modern Syria.
Early Phoenician (or proto-Phoenician) sailors may have delivered founding populations of the Cardium Pottery Neolithic migration past the Aegean to the southern coast of Europe as suggested in the following map.
The earliest Impressed Ware sites, dating to 6400-6200 BC, are in Epirus and Corfu. Settlements then appear in Albania and Dalmatia on the eastern Adriatic coast dating to between 6100 and 5900 BC. The earliest date in Italy comes from Coppa Nevigata on the Adriatic coast of southern Italy, perhaps as early as 6000 cal B.C. Also during Su Carroppu civilization in Sardinia, already in its early stages (low strata into Su Coloru cave, c. 6000 BC) early examples of cardial pottery appear. Northward and westward all secure radiocarbon dates are identical to those for Iberia c. 5500 cal B.C., which indicates a rapid spread of Cardial and related cultures: 2,000 km from the gulf of Genoa to the estuary of the Mondego in probably no more than 100–200 years. This suggests a seafaring expansion by planting colonies along the coast. 
Older Neolithic cultures existed already at this time in eastern Greece and Crete, apparently having arrived from the Levant, but they appear distinct from the Cardial or Impressed Ware culture. The ceramic tradition in the central Balkans also remained distinct from that along the Adriatic coastline in both style and manufacturing techniques for almost 1,000 years from the 6th millennium BC. Early Neolithic impressed pottery is found in the Levant, and certain parts of Anatolia, including Mezraa-Teleilat, and in North Africa at Tunus-Redeyef, Tunisia. So the first Cardial settlers in the Adriatic may have come directly from the Levant. Of course it might equally well have come directly from North Africa, and impressed-pottery also appears in Egypt. Along the East Mediterranean coast Impressed Ware has been found in North Syria, Palestine and Lebanon.It isn't entirely clear if the Analusian Neolithic was a pilot wave of the Cardial Pottery Neolithic (either a demic one with pioneer colonies that moved faster than the main wave of Neolithic expansion, or via copying by local peoples of Neolithic cultures to the east or south in a manner that managed to acquire seed crops and the skills needed to grow them, but few domesticated animals), was an extension of the Funnelbeaker Neolithic southward down the Atlantic coast that emerged out of the Linear Pottery Neolithic of the Danubian basin, or was a non-demic technology borrowing by indigenous Southern Iberians.
About 1500 years after the Andalusian Neolithic began, and in the same area, the earliest Bell Beaker people emerge abruptly into the historical scene around 3200 BCE to 3000 BCE. Like the Phoenicians, the earliest Bell Beaker people appear to have been a maritime culture. The early maritime Bell Beaker people in Andalusia and Southern Portugal, in the vicinity of the ancient city of Tartessia (in Southwest Andalusia), have from their initial appearance relatively advanced mining and metal working capacities, relatively sophisticated pottery, the capacity for reliable maritime travel, and much wider use of cattle.
At the time, they were the Bell Beaker people most advanced culture of Western Europe by far and would remain so for about two thousand years. Bell Beaker people or cultures in continuity with theirs, built Stonehenge, were a culture in which the Druids flourished, and a plausible possible sources of the Atlantis myth. The Atlantic Megalithism preceded the Bell Beaker people was continued to progress in the era of their influence to more advanced levels.
Still, we can saw with confidence that the population genetics of North Africa show only a faint demic impact from them or their descendants in a coastal region roughly from Morocco to Tunisa, and almost no influence from there to Egypt, or inland, or to the south of Morocco, in North Africa, from a people who appear likely to have had immense population genetic impact in Western and Northern Europe. So, the logical inferrence is that the Bell Beaker people's cultural package and genetic package either emerged from local innovation by autochronous peoples in Southwestern Iberia, or made it was to that location via Southern Europe rather than via North Africa.
The large population genetic influence of the Bell Beaker people that I infer is suggested by multiple lines of evidence and is consistent with the earliest ancient DNA from Bell Beaker peoples. But, we have no pre-Bell Beaker Y-DNA so our capacity to know for sure how much of an impact they had genetically from direct evidence is limited. Physical anthropology data (i.e. old skeletons) show discontinuity in physical type at the Bell Beaker to pre-Bell Beaker transition point almost everywhere but in Southern Iberia where they first appear and in the modern Czech Republic region.
Phylogeny would suggest an origin for Y-DNA haplogroup R1b that is modal in most of the former Bell Beaker territory, in the vicinity of the Balkans, the Central to Eastern European Steppe, Central Asia and the Caucasus Mountains, where Y-DNA haplogropu R1a seems to have its source. But, it is unclear how far South that R1a and R1b range went in the Copper Age and early Bronze Age.
All of this happened before Bronze Age collapse and before the earliest attested arrival of the Phoenicians in the area. Given the fact that the Phoenician path to the Western Mediterrean was North African unlike the Bell Beaker people, and that the Phoenicians arrived in Iberia only in the final waning days of cultures in continuity with the Bell Beaker people, they could not have played any meaningful role in the emergence of the Bell Beaker culture - a data point that fits the fact that none of the attested written languages of cultures in continuity with the Bell Beaker people show any similarity to the Semitic languages.
The Phonenicians in the Bronze Age Collapse Era
The Phoenicians arrival in Iberia corresponds in time roughly with the arrival of the Indo-European Urnfield and Celtic societies there (around 1300 BCE and later) when the cultures in continuity with the Bronze Age Bell Beaker culture mostly collapsed and underwent linguistic shift to Indo-European languages although with fairly modest superstrate population genetic impact (less than 10%-20% in most of the former Bell Beaker region, although not in Basque country which can be used as a point of reference regarding the pre-Indo-European population genetics of the region).
But, the Phoenicians probably did conduct trade with the Tartessians of Andalusia, who may have been one of the most long enduring holdouts of cultures in continuity with the Bell Beaker people and the remnants of the Basque culture and related peoples attested by the earliest preserved written histories of Iberia. And, Phoenicians rather than Indo-Europeans held much of the coastal Iberian territory that was previously held by the Tartessians.
Indo-European Celtic colonists in the Iron Age in Western Europe, and Indo-European Greek colonists in Eastern Iberia and Southern France would retrace many of the paths previously taken by Bell Beaker people, although much of that territory would later fall to the Romans.
At around the same time that Indo-European Italic and Greek peoples started to colonize the Italian Pennisula and Western coast of the Balkans. Recent archaeological evidence has revealed that the Biblically attested Philistines of the Southern Levant were sea people who were culturally Mycenean Greeks and were diverted there by the Egyptians. This is the time that the Indo-European Hittite Empire fell, and the most plausible time for Armenia ethnogenesis driven by the migration of Aegean Indo-European Phrygians - a cousin of the Greeks first into the vacuum in central Anatolia left by the collapse of the Hittite Empire and then beyond into what would become the homeland of the Armenians. Also, at around the same time, Indo-European Germanic peoples were expanding rapidly in Northern Europe from an epicenter in the vicinity of Denmark.
The Far Flung Iron Age Phoenician Society
The Phoenician society was a linguistically Semitic people originating in the coastal city-states such as Byblos, Tyre and Sidon that flourished from 1200 BCE to 65 BCE, establishing colonies in North Africa, Sicily, Sardinia, and Andaulsia, Spain. Almost all modern alphabets are derived from theirs. Their demise came when they were conquered by an expanding Persian empire. The Wikipedia link above recounts that:
From the 10th century BC, their expansive culture established cities and colonies throughout the Mediterranean. Canaanite deities like Baal and Astarte were being worshipped from Cyprus to Sardinia, Malta, Sicily, Spain, Portugal, and most notably at Carthage in modern Tunisia.An unsourced statement in the Wikipedia article claims that "the Phoenicians traded with . . . the Somali city-states of Mosylon, Opone, Malao, Sarapion, Mundus and Tabae," in the Second Millenium BCE (i.e. sometime between 1000 BCE and 2000 BCE).
Both of these statements are consistent with a fairly constrained scope of operations for the Phoenicians until the late Bronze Age or early Iron Age.
Relationship Religiously To Early Jews
Phoenicians would have shared a Caananite Baal worshipping religion with the pagans whom the Hebrew Bible describes the early Jews as competing with; the portion of the Ten Commandments directed at graven images was directed largely at the religion shared by their fellow Semites, the Phoenicians. The early Jews of the Hebrew Bible have a showdown with the Egyptian pagan religious establishment immediately before they leave Egypt, but never struggle over temptations to adopt Egyptian polytheism.
As the only Caananite Semitic people in regular intimate contact with Egyptians in Egypt, if the Exodus story of an origin for the Jews in Caanan via Egypt has any truth to it, it may very well be that pre-Exodus Jews either were Phoenicians or arrived in Egypt via Phoenician ships run by sailors who shared an ethnic identity with them.
Modern Jews are genetically closer to the people of the North Levant than to people of the South Levant, which would fit to a narrative of an iron age migration to the South Levant until exile from the region into a diaspora, signficant endogamy, and significant displacement of pre-existing populations there upon their arrival (as opposed to a religious conversion of a pre-existing population there followed by admixture making them indistinguishable for the local residents).
The Fall of the Phoenicians
After Alexander the Great conquered Tyre in 332 BCE, the Phoenecians ceased to be an autonomous society in their homeland, that then fell from 286 and 197 BCE to the Ptolemies of Egypt, then to the Greek Seleucids, followed by a brief period of independence: "Tyre became autonomous in 126 BC, followed by Sidon in 111." But, King Tigranes the Great of Armenia ruled Syria and Phoenicia from 82 until 69 BCE, when he fell to a Roman in 69 BCE, and in 65 BCE, Pompey finally incorporated the territory as part of the Roman province of Syria.
A significant autonomous culturally Phoenician state continued in the Western Mediterranean territory shown below based around the North African City of Carthage (close to modern Tunis), until the Romans ended Phoenician rule in this region at the end of the Punic Wars in 146 BCE. The region would then remain under Roman rule for the next five and a half centuries or so.
Some historians have claimed that the areas with large Jewish populations in the Roman era (particularly during the Jewish diaspora after the destruction of the Temple in 70 CE) often seem to coincide with areas that were Phoenician in the pre-Roman era.
Post-Roman Era Activity
In the waning days of the Roman Empire, starting around the 5th century CE, Germanic Vandal and Visigothic migrations would sweep through Iberia, and the Vandals would go further into former Phoenician territory in North Africa to mount raids from Carthage, only to fall after about a century to the local pagan Moors, after which it was reincorporated with Rome for a bit less than two centuries, after which it became part of a rapidly expanding Islamic Empire that briefly reached as far as Southern France where Charlamagne's forces finally stopped their advance.
The Islamic empire also quickly enveloped all or almost all of the former Phoenician territory in the Levant. The Crusades established short lived Christian states in much of former Phoenician territory in the Levant in the early second millenium CE, only to fall again to local Muslim regimes that were ultimately incorporated into the Ottoman Empire. The Ottoman Empire then collapsed at the end of World War I and most of the modern history of the Middle East is the story of the state system that was errected by victorious colonial powers in the aftermath of World War I. Modern population genetics show that modern Jews and Levantine Christian and Druze populations show more affinity to the historically Phoenician Northern Levant than to the Southern Levant where the Hebrew Bible describes the iron age Jewish Kingdoms as being located.