The history of these towns goes back to Canaanite, Philistine, and Roman times. Before 1948, these towns boasted numerous khans (inns) for travelers. In fact, Khan Yunis owes its name to a Mamluk official who built its large khan in the 14th century.
As recorded in 1886, Bani Suheila was a large village counting one hundred and twenty huts, partly built of stone, partly of mud, and surrounded by gardens of water-melons, figs, palms, jummez, apricots and legumes. In the north a good but deep well, worked by a camel, supplied the town with drinking water. Near the town, in Sheikh Yusuf several ancient remains, including small twisted marble columns and building stones were found. 
For centuries, the coastal area was a main thoroughfare between Egypt and the Mediterranean coast, used by traders and conquering armies alike. The trade route through Gaza to Egypt brought great economic advantage to the area. In previous centuries, the lack of restricting borders enabled unobstructed communication and travel and the intermixing of inﬂuences and styles, especially among the Bedouin tribes. This rich agricultural area prospered by settled Bedouin tribes that became active in regional trade on routes connecting Egypt, the Levant, and Arabia. Many families benefited from the increase in regional trade and became large land owners during this time. During Ottoman rule the Al Qarra clan became the largest land owning family in Southern Gaza due to their vast trade networks.
^A Survey of Palestine: Prepared in December 1945 and January 1946 for the Information of the Anglo-American Committee of Inquiry By Anglo-American Committee of Inquiry on Jewish Problems in Palestine and Europe, United Nations General Assembly. Special Committee on Palestine Published by Institute for Palestine Studies, 1991 ISBN 0-88728-211-3 p 132
^al-Sayyid Muḥammad ʻAlī Nawfal (1965) Israel's crime record Information Dept. p 28
^Morris, Benny (1993) Israel's Border Wars, 1949-1956: Arab Infiltration, Israeli Retaliation, and the Countdown to the Suez War. Oxford University Press, ISBN 0-19-829262-7 p 388