وقد بقي من يومئذ هذا الأمل مكنونا في نفوس المسلمين. ومضت الغزوات النبوية برية لم تخرج إلى البحر، ولم تعتد بلاد العرب. واستمر الأمل العزيز مكنونا كذلك، في خلافة الصديق رضي الله عنه إذ لم تزايل غزواته إلى الشام الطريق البري الذي ابتدأ رسول الله صلى الله عليه وسلم يسلكه بنفسه من تبوك.
حتى إذا أفضت الخلافة إلى أمير المؤمنين عمر بن الخطاب، رضي الله عنه واتسعت الفتوح وتعددت مسالكها، بدأ الأمل المكنون يتطلع إلى البروز، فبدأ التردد، ثم ظهر الجدال، ثم آل الأمر إلى المحاولات.
وكذلك المعارضة الشديدة في ذلك، تبدو من أمير المؤمنين عمر رضي الله عنه لشدة حذره على المسلمين، ولما كان يعلم من ضعف استعدادهم يومئذ بالنسبة إلى أعدائهم الذين كانت بيدهم أهم القواعد البحرية، فكان يرى من الجرأة المذمومة أن يغرر بالمسلمين تغريرا قد يحتمل سوء مغبته، وهو الراعي المسؤول، كما علل بذلك ابن خلدون.
أما الساعي لتحقيق فكرة الغزوات البحرية، فقد كان يضطلع بزعامته صحابيان جليلان من عمال سيدنا عمر، هما العلا بن الحضرمي، عامل البحرين، على المحيط الهندي، ومعاوية بن أبي سفيان، عامل الشام على البحر الأبيض المتوسط.
أما العلاء فقد جمع جنده من البحرين بدون إذن الخليفة، وعبر بهم البحر إلى شواطئ البلاد الفارسية، وقصد عاصمة الفرس، يومئذ وهي مدينة إصطخر، فكانت لهم مواقع عظيمة، أحرقت فيها سفن المسلمين، وحوصروا، وسدت عليهم مسالك الرجوع. وبلغ ذلك عمر رضي الله عنه فاشتد غضبه، وعزل العلاء، وأنجد الجيش المحصور بمدد من البصرة فك عنهم حصارهم، وخاض معارك جديدة حمدت آثارها.
وبهذا يتبين أن العلاء بن الحضرمي هو أول من ركب البحر غازيا في الإسلام وبذلك جزم المقريزي، إلا أن جمهور الأدباء والمؤرخين لا يعدونها في الأوليات فيقولون: أول من ركب البحر معاوية بن أبي سفيان، ولعل ضعف أثر هذه الغزوة، وخلوها عن إذن الخليفة هو الذي دعاهم إلى ذلك.
وأما معاوية فقد كان محل عمله بالشام منتهيا إلى حدود الروم، وكانت مملكة الروم الشرقية هي التي بقيت تناهض سطوة الإسلام، بعد القضاء على مملكة الفرس، في موقعة القادسية الحاسمة، وكانت عاصمة المملكة مدينة قسطنطينية قبلة أنظار العالم، بعد سقوط روما، فكان معاوية يلح على عمر رضي الله عنهما في غزوة بلاد الروم بحرا، ويذكر له قرب مواقع المسلمين من مواقع الروم. وإزاء هذا الإلحاح رأى أمير المؤمنين أن يوجد لديه شيئا يعتمد عليه للخروج من تردده، فكتب إلى عامله على مصر: عمرو بن العاص، يستوصفه البحر، فأجابه عمرو بكتابه المشهور، مؤكدا ما في نفس أمير المؤمنين من مخاوف. وعلى ذلك اعتمد عمرن ورفض إلحاح معاوية رفضا باتا، جاعلا له من قصة العلاء بن الحضرمي عبرة.
وسكت معاوية رضي الله عنه من إلحاحه بقية الخلافة العمرية، حتى إذا صارت الخلافة إلى عثمان بن عفان رضي الله عنه، أعاد استئذانه فأعرض كما أعرض الخليفة من قبله. حتى إذا تكرر إلحاح معاوية أجابه: على شرط أن لا ينتخب الناس لذلك، ولا يقرع بينهم، ولكن يخيرهم فمن تطوع بالغزو في البحر وجهه.
وبهذه الصورة تكونت أول غزوة بحرية رسمية في الإسلام سنة 28، وكانت وجهتهم الأولى جزيرة قبرص فتوجه إليها أسطول الشام، الذي جهزه معاوية بقيادة عامله على البحر عبد الله بن قيس الجاسي، وأسطول مصر بقيادة عبد الله بن أبي السرح، فاتح إفريقية. والتقى الأسطولان على قبرص فنصبا حصارا لم يرفع إلا بمعاهدة صلحية تضمنت إلزام أهل جزيرة قبرص بدفع جزية سنوية وإباحة طريقهم لقوات الإسلام إلى سواحل الروم، وإنذار المسلمين بكل خطر يتهددهم من الروم.