The history of these towns goes back to Canaanite, Philistine, and Roman times. Before 1948, these towns boasted numerous khans for travelers. Khan Yunis owes its name to a Mamluk official who built its large khan in the 14th century. 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 influences 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. Bani Suheila was marked Maatadieh Village on Jacotin’s map surveyed during Napoleon's 1799 invasion. In 1838, Edward Robinson called it Beni Sehileh, located in Gaza. In 1863, the French explorerVictor Guérin found Bani Suheila to have about 1300 inhabitants, while an official Ottoman village list of about 1870 showed 209 houses and a population of 440, though the population count included men, only. As recorded in 1886, Bani Suheila was a large village counting one hundred and twenty huts, partly built of stone, partly of adobe, 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.
British era
In the 1922 census of Palestine conducted by the British Mandate authorities, Bani Suheila had a population of 1,043 inhabitants, all Muslim, increasing in the 1931 census to 2,063, still all Muslims, in 406 houses. At the end of the Mandate period, in the 1945 statistics, Bani Suheila had a population of 3,220, all Muslims, with 11,128 dunams of land, according to an official land and population survey. Of this, 54 dunams were for plantations and irrigable land, 10,639 used for cereals, while 97 dunams were built-up land.