قالوا: لما بلغ أهل اليمن ظهور رسول الله صلى الله عليه [وسلم]«١١٦» وعلو حقه، أتته وفودهم فكتب لهم كتابا باقرارهم على ما أسلموا عليه من أموالهم وأرضيهم وركازهم «١١٧» فأسلموا ووجه اليهم رسله وعماله لتعريفهم «١١٨» شرائع الاسلام وسنته، وقبض صدقاتهم وجزية رؤوس من أقام على النصرانية واليهودية والمجوسية منهم. وكان ممن وجه من العمال المهاجر بن أبي أمية بن المغيرة المخزومي، فولاه صنعاء فقبض عليه السلام وهو عليها، وقال قوم: انما ولي المهاجر صنعاء، أبو بكر وولى خالد بن سعيد مخاليف أعلى اليمن.
وقال هشام بن الكلبي، والهيثم بن عدي: ولي «١١٩» رسول الله صلى الله عليه [وسلم]«١٢٠» المهاجر كندة، والصدف، فلما قبض رسول الله كتب أبو بكر الى زياد بن لبيد البياضي بولاية كندة والصدف الى ما كان يتولاه «١٢١» من حضرموت. وولي المهاجر، صنعاء ثم كتب اليه بانجاد زياد بن لبيد، ولم يعزله عن صنعاء وأجمعوا جميعا، على ان رسول الله صلى الله عليه وسلم، ولي زياد بن لبيد حضرموت، وولى رسول الله أبا موسى الاشعري، زبيد، ورمع، وعدن، والساحل. وولي معاذ بن جبل، الجند وصير اليه القضاء، وقبض جميع الصدقات باليمن. وولي نجران، عمرو بن حزم الانصاري، ويقال: انه ولي أبا سفيان، نجران بعد عمرو ابن حزم.