Hayatının ilk yılları hakkında bilgi yoktur. Kaynaklarda Bosna'nın Sokol köyünden olduğu, Yavuz Sultan Selim zamanında (1512-1520) kardeşi Deli Hüsrev Paşa vasıtasıyla saraya alındığı, bir süre Kanûnî Sultan Süleyman'ın berberbaşılığında bulunduğu belirtilir. Daha sonra sipahi oğlanları zümresine giren Mustafa Ağa çaşnigîrlik ve küçük mîrâhurluk yaptı. Rüstem Paşa'nın vezîriâzamlığı sırasında (951/1544) yeniden çaşnigîrliğe getirildi ve Safed sancak beyliği verilerek İstanbul'dan uzaklaştırıldı. Ardından 5 Şâban 964'te (3 Haziran 1557) Şehzade Selim'e lala oldu (BA, A.RSK, nr. 1457). Şehzade Selim ile Bayezid'in taht kavgasında etkili rol oynadı. İki kardeş arasındaki gerilimi tırmandırdı ve Selim'e avantaj sağladı. Bayezid'in Selim'e yolladığı tehdit mektuplarını İstanbul'a bildirdiği gibi padişahın Bayezid'e gönderdiği nasihatnâmeleri ele geçirip bunların şehzadeye ulaşmasını engelledi. İki kardeş arasında Konya'da meydana gelen savaşın (966/1559) ardından ortaya çıkan durumdan dolayı Vezîriâzam Rüstem Paşa'nın tepkisini çekti. Rüstem Paşa onu Selim'in lalalığından alıp Pojega sancak beyliğiyle uzaklaştırmak istedi (24 Zilhicce 967 / 15 Eylül 1560). Şehzade Selim'in araya girmesiyle Tımışvar beylerbeyiliğine nakledildi (27 Muharrem 968 / 18 Ekim 1560). Ancak bu vazifesine gitmedi ve şehzadenin yanından ayrılmadı. Yine şehzadenin sayesinde görev yeri Van beylerbeyiliği olarak değiştirildi (15 Safer / 5 Kasım). İki yıl sonra Erzurum beylerbeyi (969/1562), ardından Halep ve Şam beylerbeyi (19 Rebîülevvel 971 / 6 Kasım 1563) oldu. Uzun süre kaldığı bu görevi sırasında II. Selim'in padişah oluşuyla vezîriâzamlık ümidi belirdiyse de Sokullu Mehmed Paşa bunu önleyici tedbirler aldı. Onu İmam Mutahhar'ın isyanını bastırmak üzere serdar olarak Yemen'e gönderdi (975/1567-68). Yemen'e gitmek için Kahire'ye geçen Mustafa Paşa, vaktiyle kardeşi Ayas Paşa'nın Şehzade Bayezid olayı sırasında idamına yol açtığı için kendisine düşmanlık besleyen Mısır Beylerbeyi Koca Sinan Paşa'nın aleyhte telkinleri üzerine Sokullu Mehmed Paşa tarafından serdarlıktan azledildi. Hakkındaki şikâyetlerin tahkiki için Şam'a dönmesi istendi. Bunun üzerine Şam'a gelip birkaç ay burada kaldıktan sonra İstanbul'a gitti, hatırlı kimseler sayesinde affedildiği gibi altıncı vezir oldu. Lalalığını yaptığı ve bir bakıma tahta geçmesini sağladığı II. Selim'in Kıbrıs seferine çıkma isteğinin en hararetli destekçisi oldu. Vezîriâzam Sokullu Mehmed Paşa'nın muhalefetine rağmen Venedik'e savaş ilân edilip Kıbrıs seferi açıldığında bu harekâtın serdarlığına getirildi. Kıbrıs'ta uygulanacak savaş planlarını hazırlayıp kuşatılacak kalelerin tesbitini yaptı. Onun isteği doğrultusunda Lefkoşe Kalesi'nin kuşatılmasına karar verildi. Kalenin durumunu İstanbul'a rapor eden Mustafa Paşa burayı 8 Rebîülâhir 978'de (9 Eylül 1570) ele geçirdi. Ardından Magosa kuşatıldı ve 9 Rebîülevvel 979'da (1 Ağustos 1571) alınıp Kıbrıs'ın fethi tamamlandı.
İstanbul'a döndüğünde Vezîriâzam Sokullu Mehmed Paşa'nın desteğini alan Mustafa Paşa rakibi Koca Sinan Paşa'ya karşı durumunu kuvvetlendirdi. 985'teki (1577-78) İran seferi ikisi arasında çekişmeyi iyice arttırdı. Bu çekişme aynı zamanda Sokullu'nun yerine kimin geçeceği konusunda da belirleyici olacaktı. Rekabetin hızlanması üzerine önce her ikisi de sefere gitmekle görevlendirildi; Mustafa Paşa Erzurum, Sinan Paşa Bağdat taraflarından İran'a girecekti (22 Şevval 985 / 2 Ocak 1578). Fakat bu durum her iki veziri de hoşnut etmedi, ihtilâfın daha da artması üzerine Sokullu Mehmed Paşa devreye girip Koca Sinan Paşa'yı görevden aldı ve Lala Mustafa Paşa'yı Gürcistan üzerinden Şirvan'ın fethiyle tek yetkili serdar olarak vazifelendirdi. 27 Muharrem 986'da (5 Nisan 1578) Üsküdar'a geçen Mustafa Paşa, İran sınırlarına ulaştığında Çıldır'da Safevî öncü kuvvetlerini mağlûp etti (5 Cemâziyelâhir 986 / 9 Ağustos 1578), ardından Tiflis'e girdi. Kür suyu üzerinde Koyungeçidi mevkiinde bir başka Safevî gücü daha bozguna uğratıldı. Mustafa Paşa askerin geri dönme isteğine karşı çıkıp onları yatıştırdı ve giriştiği harekâtı tamamlamak üzere Şirvan'a yürüdü. 13 Receb'de (15 Eylül) Ereş'e girdi ve daha sonra Şirvan'ın fethi gerçekleşti. Alınan yerler dört beylerbeyiliğe (eyalet) ayrıldı. Mustafa Paşa, Safevî beylerini Osmanlı tarafına çekmek için çeşitli girişimlerde bulunup fethedilen yerlerde kalıcı bir yerleşmeyi sağlamaya çalıştı. Dağıstan ve Gürcü beylerinin itaatini sağladıktan sonra kışı geçirmek üzere Erzurum'a döndü. Bu sırada 1578 yılının son günlerinde gelen emirler üzerine Kars Kalesi'nin tamiri ve sınır boylarının takviyesi için Kars'a giden Mustafa Paşa kalenin inşasını tamamladı (29 Cemâziyelâhir 987 / 23 Ağustos 1579). Bir süre burada kalıp ekim ayında Erzurum'a döndüğünde Sokullu Mehmed Paşa'nın öldürüldüğü haberini aldı. Çok geçmeden de rakibi Koca Sinan Paşa'nın tahrikleri neticesinde serdarlıktan azledildi (Zilkade 987 / Ocak 1580). İstanbul'a döndüğünde padişahın huzuruna çıkma isteği kabul görmedi. Ancak Vezîriâzam Ahmed Paşa'nın vefatı ve Koca Sinan Paşa'nın İran seferine çıkması, o sırada merkezde divanda tecrübeli bir vezirin bulunmaması gibi sebeplerle sadâret kaymakamlığına getirildi. Koca Sinan Paşa'nın baskısı ile vezîriâzamlık kendisine verilmedi ve sadâret mührü Sinan Paşa'ya gönderildi. III. Murad, Mustafa Paşa'ya sadâret kaymakamı olarak vezîriâzam gibi hareket etme yetkisini verdiyse de o bundan memnun kalmadı. Yaşı yetmişi geçmiş olan Mustafa Paşa az sonra 25 Cemâziyelâhir 988'de (7 Ağustos 1580) vefat etti. Tarihçi Âlî Mustafa Efendi, onun öleceğini hissedip on yedi gün önce Eyüp'te mezar yerini satın aldığını belirtir.
Kaynaklarda akıllı ve tedbirli bir devlet adamı olarak anılan Mustafa Paşa, Mısır Sultanı Kansu Gavri'nin oğlu Mehmed Bey'in kızı Fatma Hanım'la evlenmiş, ondan olan oğlu Mehmed Paşa Halep beylerbeyiliğine kadar yükselmiştir. Ayrıca Kanûnî Sultan Süleyman'ın oğlu Şehzade Mehmed'in kızı Hümâ Sultan ile evliliği (18 Cemâziyelevvel 983 / 25 Ağustos 1575) dolayısıyla hânedana akraba olmuştur. Mustafa Paşa'nın birçok hayratı ve vakıfları bulunmaktadır. Erzurum'da bir külliye (970/1562-63); Şam'da 360 hücreli han (Lala Paşa Hanı), hamam ve tekkeler; yine Şam civarında Kuneytıra'da cami ve imaret; Konya Ilgın'da cami, bedesten, kervansaray; Tiflis ve Kars'ta şark serdarlığı sırasında yaptırdığı iki cami başlıca eserleri arasında yer alır. Ayrıca Lefkoşe'deki Ömeriye Camii'ne vakıflar tahsis etmiştir. Magosa'da fetih sonrası katedralden çevrilen cami onun adını taşır. Mekke ve Medine'de de bazı hayratı vardır. Âlî Mustafa Efendi uzun yıllar onun hizmetinde bulunmuş ve İran seferi sırasındaki faaliyetlerini Nusretnâme adlı eserinde anlatmıştır.
Kaynak: Türkiye Diyanet Vakfı İslam Ansiklopedisi