15اسلام پيوستند، چنان‌كه قبيله نخع در نبرد قادسيه حدود يك چهارم آنان را تشكيل مى‌داد. با ساخته شدن كوفه، آنان همراه مذحج در جنوب مسجد كوفه استقرار يافتند.
از اين پس تا هنگام قيام ضد «عثمان» درباره مالك اطلاعاتى وجود ندارد. او از شخصيت‌هاى مطرح يمن در عراق، و از كسانى بود كه در قيام ضد خليفه سوم، عثمان، نقش داشت. او دو بار به سبب اعتراض به عملكرد و سخنان والى عثمان، «سعيد بن عاص» اموى و «وليد بن عقبه» اموى در كوفه، و نيز عملكرد خليفه سوم در عدول از سيره رسول‌خدا(ص)، همراه برخى كوفيان همانند «كميل بن زياد نخعى»، به «دمشق» و «حمص» تبعيد شد. 1 در شام «معاويه» از ميان تبعيدشدگان، مالك اشتر و «عمرو بن زراره» را به دليل گفتن سخنان كوبنده زندانى كرد. 2
مالك پس از بازگشت به كوفه - در غياب سعيد بن عاص اموى، والى كوفه، - مانع بازگشت سعيد بن عاص اموى به آن شهر شد و بدين ترتيب بر كوفه تسلط يافت. 3 پس از آن مالك در رأس ده‌ها نفر، از كوفه به مدينه رفت و در محاصره عثمان، كه منجر به قتلش شد، شركت كرد. 4