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