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