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