'Abdullah b. Buraida melaporkan atas kebenaran bapanya bahawa Ma'iz b. Malik al-Aslami mendatangi Rasulullah (ﷺ) dan berkata:

Rasulullah, saya telah menzalimi diri sendiri; Saya telah berzina dan saya sungguh-sungguh menghendaki agar anda menyucikan saya. Dia memalingkannya. Pada hari berikutnya, dia (Ma'iz) kembali menghampirinya dan berkata: Wahai Rasulullah, aku telah berzina. Rasulullah (ﷺ) menjauhkannya untuk kedua kalinya, dan mengirimnya kepada kaumnya dengan berkata: Adakah anda tahu jika ada yang tidak kena dalam fikirannya. Mereka menafikan ada perkara seperti itu dan berkata: Kami tidak mengenalnya tetapi sebagai orang baik yang bijak di antara kami, sejauh yang kami dapat menilai. Dia (Ma'iz) datang untuk ketiga kalinya, dan dia (Nabi saw) mengirimnya seperti yang dia lakukan sebelumnya. Dia bertanya tentang dia dan mereka memaklumkan kepadanya bahawa tidak ada yang salah dengannya atau dengan fikirannya. Ketika itu adalah keempat kalinya, parit digali untuknya dan dia (Nabi saw) mengadili tentangnya dan dia bijak dilempari batu. Dia (perawi) berkata: Ada datang kepadanya (nabi) seorang wanita dari Ghamid dan berkata: Wahai Rasulullah, saya telah berzina, jadi bersihkanlah saya. Dia (Nabi saw) memalingkannya. Pada hari berikutnya dia berkata: Rasulullah, Mengapa kamu memalingkan saya? Mungkin, anda memalingkan saya semasa anda memalingkan Ma'iz. Demi Allah, saya telah hamil. Dia berkata: Baiklah, jika kamu memaksanya, maka pergilah sehingga kamu melahirkan (anak itu). Semasa dia dilahirkan, dia datang bersama anak itu (dibungkus) dengan kain dan berkata: Inilah anak yang telah aku melahirkan. Dia berkata: Pergilah dan menyusukannya sehingga kamu menyapihnya. Ketika dia menyapihnya, dia datang kepadanya (nabi) dengan anak yang memegang sepotong roti di tangannya. Dia berkata: Rasul Allah, di sinilah dia seperti saya telah menyapihnya dan dia makan makanan. Dia (Nabi saw) mempercayakan anak itu kepada salah seorang Muslim dan kemudian menjatuhkan hukuman. Dan dia dimasukkan ke dalam parit hingga ke dadanya dan dia memerintahkan orang-orang dan mereka melemparkannya ke batu. Khalid b Walid maju ke depan dengan batu yang dilemparkan ke kepalanya dan di sana menyemburkan darah di wajah Khalid sehingga dia menyalahgunakannya. Rasulullah (ﷺ) mendengar sumpahannya (Khalid) yang telah dilemparkan kepadanya. Setelah itu dia (Nabi saw) berkata: Khalid, bersikap lembut. Demi Dia di tangan Yang menjadi hidupku, dia telah membuat pertobatan sehingga walaupun seorang pemungut cukai yang salah bertobat, dia akan diampuni. Kemudian memberikan perintah kepadanya, dia berdoa kepadanya dan dia dikebumikan.