The Arabs were already sailing on the Red Sea and Persian Gulf in pre-Islamic times but they were not greatly experienced seafarers in contrast to the Persians. This soon changed as their struggle to conquer Byzantium turned into a naval contest in the Mediterranean. Assisted by Persians and the Copts of Egypt, the Arabs hastened to develop a navy which they used to defeat the Byzantines at the Battle of the Masts in 655 and to besiege Constantinople shortly afterwards. Although Constantinople’s sea defences were too strong for the Muslims, they rapidly evicted their Byzantine rivals from other Mediterranean ports and islands as they sailed ever further west.
For centuries, power in the Mediterranean had depended on naval might. At the end of the 6th century the Byzantine Empire dominated both the Mediterranean and the Black Seas with naval bases at Carthage, Alexandria, Acre and Constantinople. Yet the number of Byzantine warships remained few, because the Empire faced no serious maritime rivals until the Sassanian occupation of Egypt and Syria. Even more threatening were the subsequent Muslim conquests of these areas, as well as North Africa and, eventually, the Iberian Peninsula.
In the Islamic forces' first major naval operation in the Mediterranean, they temporarily occupied the island of Cyprus after having driven off a Byzantine fleet near Alexandria in 652 - their first naval victory. Then, in 655, the Islamic fleet won a convincing victory over the Byzantine navy off the south-western coast of what is now Turkey. For nigh on a thousand years Greeks and then Romans had dominated the Mediterranean Sea. Now, in the first major Mediterranean sea battle for centuries, an Arab fleet had successfully challenged the Byzantines in their home waters.
Surprisingly, given the relative inexperience of the Muslim fleet, this battle saw the Byzantines defeated both at sea and in a skirmish on shore at the same time. This clash in 655 near Cape Chelidonia, off the Lycian coast, came to be known as the 'Battle of the Masts' because the Muslims had landed to cut tall trees for the masts and yards of their new fleets, based in Egypt and Syria. A lack of suitable large timber would in fact hamper Muslim naval development throughout the medieval period, though it did encourage technological innovation in Islamic naval architecture. During this encounter the Byzantine ships seem either to have been moored in close formation or to have been tied together. As a result the Muslims were able to win because of their superior boarding and close-combat tactics.