1592'de Arnavutluk'ta doğdu. Yeniçeri ocağından yetişti. Çorbacılık ve kul kethüdalığı yaptı. 1633-34 yılında sekbanbaşı ve Mart-Nisan 1635'te yeniçeri ağası olan Kemankeş Kara Mustafa Paşa, 17 Ekim 1635'te Kaptan-ı Derya, Aralık 1638'te Sultan Dördüncü Murad döneminde de sadrazam oldu. Bağdat Seferi sırasında, padişahın her konuda danıştığı paşalardan biri oldu. Bağdat seferi sonunda Kasr-ı Şirin antlaşmasını imzalayarak İstanbul'a döndü. Devlet teşkilatında geniş bir ıslahat yapmayı tasarladı.
Gelir ve giderleri ayarlayarak sarayda tasarruf yapılmasını sağladı. Paşanın bu davranışları bazı kişilerin çıkarlarına dokundu. Kösem Sultan'ın Mustafa Paşa hakkındaki entrikalarına, Cinci Hoca ve Silahdar Yusuf Paşa'nın çalışmaları eklenince, Sultan Birinci İbrahim'in emriyle 26 Ocak 1644'te idam edildi. Mezarı Parmakkapı'da kendi yaptırdığı medresededir. Yiğit, cesur ve tedbirli bir devlet adamıydı. Ayrıca Kurşunlu Mahsen'deki bir kiliseyi camiye çevirtti. Tokat'ta Mehmed Paşa Hanı'nı tamir ederek cami ve hamam yaptı. 500 ev inşa ederek Sivas Yenişehrini meydana getirdi. Eğri'de büyük bir hamam, mektep, sayısız çeşmeler ve Edirne'de Köse Mihal köprüsünü yeniden yaptırdı.