Coba jelasin Langkah-langkah awal (673-674) dari Pengepungan Konstantinopel (674–678) dong

Aksi militer tahun 669 membuat bangsa Arab sadar bahwa mereka sebenarnya berpeluang untuk melancarkan serangan secara langsung terhadap Konstantinopel, dan bahwasanya mereka perlu memiliki pangkalan logistik yang tidak terlampau jauh dari kota itu. Pangkalan logistik didirikan di Semenanjung Kizikos, yang terletak di pesisir selatan Laut Marmara, tempat armada tempur di bawah pimpinan Fadhalah bin 'Ubaid berlabuh sepanjang musim dingin tahun 670 atau 671. Mu'awiyah pun mulai berancang-ancang melancarkan serangan penghabisan terhadap ibu kota Kekaisaran Romawi Timur. Berbeda dari aksi militer yang dipimpin oleh Yazid, Mu'awiyah berencana mendatangi Konstantinopel lewat jalur pesisir. Pelaksanaannya harus seksama dan bertahap. Pertama-tama kaum Muslim harus menguasai titik-titik penting, dan mendirikan pangkalan-pangkalan di sepanjang daerah pesisir. Selanjutnya dari pangkalan mereka di Kizikos, kaum Muslim harus memblokade Konstantinopel di darat maupun di laut, sehingga tidak dapat lagi menerima pasokan bahan pangan dari daerah-daerah pertanian di pedalaman.

Pada tahun 672, tiga armada besar kaum Muslim akhirnya dikerahkan untuk mengamankan jalur-jalur laut dan mendirikan pangkalan-pangkalan di antara Syam dan Kepulauan Aegea. Armada yang dipimpin oleh Muhammad bin Abdullah berlabuh sepanjang musim dingin di Smirna, sementara armada yang dipimpin oleh Qais (mungkin Abdullah bin Qais) berlabuh sepanjang musim dingin di Likia dan Kilikia. Armada ketiga yang dipimpin oleh seorang bernama Khalid akan menyusul dan bergabung kemudian. Menurut laporan Teofanis, Kaisar Konstantinus IV (memerintah 661-685) mulai menyiagakan armadanya begitu mendengar kabar kedatangan armada-armada Arab. Armada tempur Romawi Timur diperkuat pula dengan sejumlah kapal pengangkut tangki dan pipa yang akan digunakan untuk mengoperasikan senjata pembakar terbaru, yakni api Yunani. Pada tahun 673, armada Arab lain di bawah pimpinan  merebut Tarsus di Kilikia, dan Rodos. Pulau Rodos, yang terletak di antara Syam dan Konstantinopel, dijadikan pangkalan pasokan terdepan sekaligus pusat serangan laut kaum Muslim. Garnisun pangkalan yang beranggotakan 12.000 orang prajurit secara teratur dirotasi kembali ke Syam, satu armada kecil disiagakan untuk menjaga pangkalan sekaligus untuk dikerahkan dalam aksi-aksi serangan dadakan. Orang-orang Arab bahkan membuka lahan-lahan gandum dan mendatangkan ternak untuk digembalakan di pulau ini. Kekaisaran Romawi Timur berusaha menghalang-halangi rencana bangsa Arab dengan melancarkan serang laut terhadap Mesir, tetapi gagal. Selama kurun waktu ini, aksi-aksi serangan dadakan di daratan Asia Kecil terus berlanjut, bahkan pasukan Umayyah melewatkan musim dingin di dalam wilayah Kekaisaran Romawi Timur.