Gaza, or Azza as it was known in Tanach (the G sound we use today probably originates from the gutteral Ayin, which the Sefardim still pronounce properly, which makes a G sound, hence the fact that Sodom and Amorah became Sodom and Gamorrah) was inhabited by people originating from the Island of Crete in the Mediterranean (I heard else where they were from Cyprus – yet we should just assume they came from the Mediterranean) The Cretans began to be known as the Plishtim (philistines) and Avimelech was the king there. Perhaps you see this relevance to some of the things mentions about the Plishtim in Sefer Beraishes. Avraham had a well that made him prosper and Avimelch comes forward and has his soldiers fill up the well as part of a land dispute. So, Avraham built a new well, this time too the soldiers of Avimelech came and filled up the well, saying that the land that Avraham owned belonged to them, although they were just jealous. This repeated itself over and over and after 7 wells eventually Avimelech came to make peace. They named the place of the well Beer Sheva – 7 wells. Years later Yitzchak has a similar encounter with the Plishtim. He too dug wells and prospered, only to get the well filled by the Plishtim. He buildt another well, only for it to be blocked up again. He then built a third well, this time however it remain open. The fact that the third well survived symbolizes that after two temples were destroyed, the third one would exist forever.
The Plishtim where often at war with the Jews in the times of Tanach. As the Plishtim were not one of the seven Canaanite nations, having come from the Mediterranean not Canaan, Yeshuah and Bnei Yisrael never gave them the ultimatum they gave the other seven nations, so the Plishtim lived next to the Jews. Shimshon HaGibbur was involved with Azza.
Next Weeks question: What City has the most names, and how many of its names can you name?
P.S. The term Palestinian is not the English version of Plishtim as the two groups of people are different. During or after the time of the Bais Hamikdash, the Romans (and perhaps other nations) bergan calling Eretz Yisroel Palestine. The modern day Palestinians are, to the best of my knowledge descendants of Beduins and other nomads that came from Arabia, Ishmalites as they used to call them. (I stand to be corrected however). The English name for Plishtim is Phillistines.