The word "Palestinian" derives from the Philistines, a people who were not indigenous to Canaan but who had gained control of the coastal plains of what are now Israel and Gaza for a time. According to ancient Egyptian records of the period, which is the first written mention of them, the Philistines reached the region in around the 12 century BCE, which the archaeological record seems to confirm.
Although it is likely that some Philistine blood runs through the veins of modern-day Palestinians (and through the Jews'), they are a different people with a different culture.
Where the Philistines originated is a matter of debate, as they left no written records, but there are two main theories, based mainly on signature pottery shards. The original theory was that the Philistines originated in the Aegean basin and belonged to the Mycenaean culture. A newer hypothesis is that they were members of the Hurrian culture and came from what is today southern Turkey and Syria.
In any case, given the current state of knowledge, it is impossible to determine the etymology of the Philistines’ name in their own language.
What we can discuss is how this word morphed into the name of an altogether different people thousands of years later.
Merging with the Canaanites
The Philistines feature prominently in the Bible as the main enemy of the early Israelite kingdoms, mostly in the Book of Samuel, where they are described as an advanced civilization with a monopoly on iron manufacture. Yet like the kingdoms of Israel and Judah, they were unable to sustain their independence once the great empires of Mesopotamia entered play.
After some 600 years of living on the coast and sporadically fighting with the Israelites, in the 6th century BCE the region fell under Assyrian and Babylonian rule.
The Philistine people living in these parts merged with the local Canaanite population, causing their distinct culture to forever disappear in this region. But the Philistines' name endured as the name of the territory they had occupied - the coastal plains of southern Canaan.
Meanwhile, in Greece, the Greeks adopted the name "Philistia" to refer not only to the coastal plains on the other side of the Mediterranean Sea but to the inland regions as well. A notable example of this expanded use appears in Aristotle's book “Meteorology,” where in the 4th century BCE, the great philosopher described a lake in Philistia in which “if you bind a man or beast and throw it in it floats and does not sink...so bitter and salt that no fish live in it and that if you soak clothes in it and shake them it cleans them.” The Dead Sea which he is describing is far away from the original home of the Philistines.
In the 330s and 320s BCE, Alexander the Great vanquished the Persian Empire, which had supplanted the Babylonians in the region, and the Hellenistic period began. From that point, Greek began to supersede Aramaic as the dominant language of the Middle East. This in turn made the name "Philistia" more popular in the region, though Philistia was not a uniform polity. It was divided into districts and subordinate kingdoms, each with limited autonomy. Control over them swung between the Hellenistic kingdom based in Egypt, and the competing Hellenistic kingdom in Syria.
During a brief period of Jewish independence, Alexander Jannaeus, the King of Judea (reigned 103 BCE to 76 BCE), managed to wrest control over most of the area. But a new power on the international scene was soon to take over - Rome.
The Arabs adopt the Greek name from the Romans
Under the Romans, Philistia remained divided into subservient polities, one of which was Judea. The Jews did not sit easy under Roman rule. After finally subduing the Jewish rebels once and for all in 135 CE following the Bar Kochba Revolt, Roman Emperor Hadrian restructured the region, uniting the provinces of Philistia and the Roman provinces in Syria, creating a single massive province called “Syria Palaestina.” Thus the unofficial Greek appellation turned into the official Roman one.
This Greek-cum-Latin name for the region was later adopted by the Arabs who conquered the area in the 7th century, and thus the Arabic name for the region, Falestin, was born. In Europe, the Latin name Palaestina slowly morphed into the different names for the region in the Romance tongues that arose from Latin, such as French and Spanish. Other non-Romance languages such as German and English got their names for the region from Latin or the Romance languages. That is how the English word Palestine came about.
At the end of World War I, the territory of the Ottoman Empire was divided between the French and the British, in accordance with the Sykes–Picot Agreement of 1916. When the British gained control of the region, at the close of World War I they adopted the name “Palestine” and its inhabitants Jewish, Muslim or otherwise were known as Palestinians. And then, during the 1920s, the nascent Palestinian national movement adopted the appellation "Palestinian" (al-Filasniyyūn) as its own.
In a twist of fate, most of the territory that had been controlled by the Philistines is now part of Israel, except for Gaza, while most of the territory that was the ancient Kingdom of Israel is currently in the West Bank and is, to a great extent, a part of the Palestinian Authority.