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