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