The name "Souda" comes from the Latin word "Suda", which means "trench", or "narrow passage".  There is limited information about Souda during the Arab Empire and the second Byzantine Period of Crete.  The wider region of Aptera was assigned to the temple of Patmos at the end of the 12^th century, establishing there one of its most important glebes.  The gulf of Souda was used as a disposal area for the opposing armies after the assignment of Crete to the Venetians during the 13^th century. According to records, a first fortification of the island was constructed in about 1230; however, this information is not supported by further evidence. The Florentine monk C. Buondelmondi visited the area in 1415 and reported the existence of salt sources in the gulf of Souda. He also reported the existence of a temple of St. Nicolas on the island, where Augustine monks lived. The island was named "Isoloto dei Frati" (Island of Brothers) after them, or "Fraronisi". The salt sources, which according to Byzantine records produced a large amount of salt, were rented to private owners during the Venetian period. The Turks called the area "Touzla", which means "salt sources" in the Turkish language ("touz" means "salt" in Turkish). In1870 Pasha Reouf dried the salt sources and built a settlement on their place, named "Azizie" in honor of the Sultan Abdul Aziz. 150 families were established in the settlement, built on the islet of the fortress. Back then, the settlement was a separate municipality and today the area is called "Kato Souda".

Throughout the 16^th century, the Turks continue to expand in the region of the east Mediterranean and it becomes obvious that the occupation of Crete is one of their main goals.  At the same time, Venice is preoccupied with the construction of numerous fortifications of cities and of other strategic regions of the island. In 1520 the fortification of the islet of Souda is designed. In 1538 the pirate  Hairentin Barbarossa  disembarks in Souda, looting and burning down the region of Apokoronas. The looting is once again repeated in 1571 from the Algerian Ouloutz Ali.  This event obliges the government to take action. From the numerous fortification proposals, the government selects the one designed by Latino Orsini, who supervises the first phase of the construction. The islet of Souda is then fortified and an underwater sea wall called "Porporella" is also constructed opposite from the islet. 

In 1645,  after a short battle the region of Chania are occupied by the Turkish army and in 1669 the invasion of the island of Crete is succeeded. Venice surrenders on the condition to keep the fortified islets of Grambousa, Souda and Spinalogga in its possession. The gulf of Souda will then become the headquarters of the Venetians in Crete. After the Turkish occupation, the reinforced guard and the local revolutionaries along with their families lived on the islet under very bad conditions for a long period. During the last Venetian-Turkish war, the fortress of Souda resisted heroically for 72 days, until it finally surrendered to the Turks in September 27, 1715. During the Turkish period, the port of Souda continued to function and service the new rulers of Crete. It became an army station, a disposal area and a permanent supply center of the Ottoman army. After the "explosion" of the Greek Revolution in 1821, the port of Souda became a central battlefield between Turks and Greeks.

In the years of Cretan governance, the port of Souda was a main disposal area for the armies of the Great Powers, who were the supervisors of the new autonomous Cretan state. The great welcome ceremony of the commissary of the Cretan state, Prince George, was held in Souda in 1898. Finally, on the islet of Souda the last act of the Turkish presence in Crete was performed, when in February 14, 1913 the Greek flag replaced the Turkish flag on the islet.