لأقتله به، إنه تأول فأخطأ (1). قال: فاعزله. قال: ما كنت أشيم سيفا سله الله عليهم أبدا " (2) (3).
ولما التقى عمر خالدا، قال له: " قتلت امرأ مسلما ثم نزوت على امرأته، والله لأرجمنك بأحجارك، ولا يكلمه خالد بن الوليد " (4).
هذه هي قصة البطاح أو قصة خالد وليلى!! وهي قصة ثابتة في التاريخ (5).
وإسلام مالك لا ينكره إلا معاند، فمما سبق يمكننا أن نعرف كثرة الذين شهدوا بإسلامه، وهم: أبو قتادة الأنصاري، عبد الله بن عمر، عبد الرحمن بن عوف، عمر بن الخطاب، أبو بكر، وخالد نفسه فيما ورد من حواره مع ابن عوف، وأضف لهؤلاء شهادة مالك وقومه على أنفسهم بأنهم مسلمون، وهي كافية لرفع السيف عنهم، وشهد بإسلامه: الواقدي، وابن عبد البر، وابن الأثير في أسد الغابة وابن كثير في تاريخه، (6) والقوشجي في شرح التجريد، وغيرهم.
يقول ابن الأثير: " ويدل على أنه لم يرتد، قول عمر لخالد: قتلت امرأ مسلما، وأبو قتادة يشهد انهم أذنوا وصلوا، وأبو بكر يرد السبي ويعطي دية مالك من بيت المال، فهذا جميعه يدل على أنه مسلم!! فرحمه الله تعالى " (7).