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