Lala Mustafa Paşa, 1500 yılında Bosna'nın Sokoloviç kasabasında dünyaya geldi. Kara Mustafa Paşa olarak da bilinmektedir. Sokollu Mehmed Paşa'yla aynı köydendir. Ağabeyi Vezir Deli Hüsrev Paşa'nın aracılığıyla Yavuz Sultan Selim zamanında devşirme olarak saraya alınmış ve Enderun'da yetiştirilmiştir.
Sarayda berberlik yaparken, Kanuni Sultan Süleyman'ın dikkatini çekmiştir. Mirahorlu-ı saniliğe kadar yükselen Lala Mustafa Paşa, 1555 yılında Rüstem Paşa'nın sadrazam olmasının ardından önce çeşnigirbaşılığa indirildi. Ardından çeşitli entrikalara karıştığı gerekçesiyle, sancakbeyi olarak İstanbul'dan uzaklaştırıldı. Bu dönemde Filistin-Safed Sancakbeyi olarak görev yaptı.
1556 yılında o dönem Manisa sancakbeyi olan Şehzade II. Selim'in lalalığına atandı. Selim'in tahtın tek varisi olmasında büyük rol oynadı. Bu görevi sırasında Selim'in kardeşi Bayezid ile arasının açılmasına neden oldu.
Lala Mustafa Paşa, daha önce Bayezid'in hizmetinde bulunmuştur. Bayezid'i babasına kardeşi Selim'i kötüleyen mektuplar yazmaya teşvik etmiştir. İki kardeşin arasının açılması üzerine ortamı yatıştırmak için Selim'i Konya'ya, Bayezid'i Amasya'ya atayan Kanuni, Lala Mustafa Paşa'yı Selim'in yanına göndermiştir.
Kütahya'dan ayrılmak istemeyen Bayezid, Amasya'ya gitmek zorunda kalınca yolda asker toplamaya başladı. Kardeşi Selim'in topladığı ordu ile 1559 yılında Konya'da savaştı. Bu çarpışmada Mustafa Paşa, Bayezid'a karşı savaştı. Bayezid yenilerek, Amasya'ya kaçmak zorunda kaldı.
Lala Mustafa Paşa 14 Eylül 1560'ta önce Budin-Pojega sancakbeyliğine, daha sonra Van beylerbeyliğine atandı. Erzurum, Halep ve Şam beylerbeyliklerinde de bulunan Lala Mustafa Paşa, 1567 yılında Yemen'i işgal eden Zeydi imamlarından Topal Mutahhar'a karşı savaşacak ordunun Serdar-ı Ekremlik'ine getirildiyse de rakiplerinden olan Koca Sinan Paşa'nın neden olduğu çeşitli aksaklıklar nedeniyle bir türlü sefere çıkamayınca 1568 senesinde görevden alındı.
İstanbul'a dönmesinin ardından bağışlanarak kubbealtı veziri olarak Divan-ı Hümayun'a giren Lala Mustafa Paşa, Sadrazam Sokullu Mehmed Paşa'nın karşı koymasına rağmen padişaha Kıbrıs'ın fethedilmesi gerektiğini kabul ettirdi. 15 Mayıs 1570 tarihinde Kıbrıs'a doğru yola çıktı. Piyale Paşa komutasındaki donanma ile birlikte komutasındaki yaya 60.000 kişiden oluşan Osmanlı Ordusu'nu, 2 Temmuz 1570'de Limasol'a çıkardı. Eylül 1570'te Lefkoşa'yı, Ağustos 1571'de de Magosa'yı alarak Kıbrıs'ın fethini tamamladı. 15 Eylül 1571'de adadan ayrılarak İstanbul'a döndü.
1578 yılında Gürcistan ve Şirvan'ı Osmanlı topraklarına katmak için İran seferine çıktı. Erzurum'da Diyarbakır beylerleyi Özdemiroğlu Osman Paşa'nın da kendisine katılmasının ardından Gürcistan içlerine ilerleyerek 24 Ağustos 1578 tarihinde Tiflis'i alan Lala Mustafa Paşa, Şirvan'ın da ele geçirilmesinin ardından Anadolu'ya döndü.
İbrahim Peçevi, Mustafa Paşa'nın İran Seferi hakkında şunları söylemiştir:
''İranlılar, ondan yedikleri dayağı hiçbir serdârdan yemediler!''
Sokullu Mehmed Paşa'nın ölümü üzerine İstanbul'a çağrıldı ve ikinci vezir olarak görevlendirildi. Sadrazam Şemsi Ahmet Paşa'nın ölümüyle 28 Nisan 1580 tarihinde sadrazam oldu. Lala Mustafa Paşa, 7 Ağustos 1580 tarihinde İstanbul'da hayatını kaybetti.
Evlilikleri
Lala Mustafa Paşa, ilk evliliğini Memlük Hükümdarı Kansu Gavri'nin oğlu Mehmed Bey'in kızı Fatma Hatun ile yaptı. Bu evliliğinden olan oğlu Mehmed Paşa, babasının vefatından beş yıl önce Halep Beylerbeyi iken hayatını kaybetti.
İkinci evliliğini Kanuni Sultan Süleyman'ın oğlu, Şehzade Mehmed'in kızı Hümaşah Sultan ile yaptı. Bu evliliğinden Sultanzade Abdülbaki Bey isimli bir oğlu oldu.