تحرك بجنوده من المدينة متجهاً نحو الجنوب الشرقي ماراً بمحاذاة الطائف من الناحية الشرقية، حتى إذا وصل نجران اتجه نحو الشمال الشرقي باتجاه عمان مشكلاً بذلك نصف دائرة مفتوحة نحو الشمال باتجاه الربع الخالي، ثم مالبث أن ولى وجهه شطر اليمن باتجاه الجنوب الغربي ماراً من شمالي مهرة وشمالي حضرموت(1).

التقى عرفجة مع حذيفة بن محصن الغلفاني في عمان. وانضمت إليهما هناك بعض القوات التي ثبتت على دينها من تلك المنطقة، كما انضمت قوات عكرمة بن أبي جهل الذي فشل في مهمته في اليمامة. أصبح هذا الجيش يضم عدداً كبيراً من المقاتلين من السهل التغلب بهذه الكثرة على جموع المرتدين. قاد معركة القتال في هذه المنطقة كقائد عام حذيفة بن محصن الغلفاني، ولكن عرفجة عاد فاستلم قيادة هذا الجيش في مهرة، وانتصر على المرتدين(2)، ثم عاد إلى المدينة. ومن هنا أيضاً أرسل لمساعدة العلاء بن الحضرمي في البحرين، وانضم إليه، ثم أرسل بمهمة إلى شواطئ فارس، وكان القائد الأول الذي جاس مياه بحر فارس، واستولى على جزيرة بحرية، وأعلن الشعائر الدينية فيها، وأقام مسجداً(3). ثم حارب فيما بعد في جبهة العراق بخاصة في معركة البويب(4).

قاتل فيما بعد في زمن عمر بن الخطاب في العراق مع المثنى، ومع سعد بن أبي وقاص في القادسة، واشترك في فتح تكريت، وفي فتح بعض المدن الفارسية مثل "رامهرمز" و "تستر" وقاتل في زمن عثمان في بلاد فارس، ثم استقر والياً في الموصل.