Lala Mustafa Paşa Bosna'nın Sokol kasabasında doğdu. Vezir olan büyük kardeşinin yardımı ile Yavuz Sultan Selim zamanında Enderun'a girdi. Berber olarak çalışırken, Kanuni Sultan Süleyman'ın dikkatini çekti. Daha sonra çeşnigir ve mirahorluk yaptı. Bazı entrikalara karıştığı için sancakbeyi olarak saraydan uzaklaştırıldı.
Manisa'da sancakbeyi olarak bulunan Şehzade Selim'in (Sultan İkinci Selim) lalalığına atandı. Bu görev sırasında Şehzade Selim'in kardeşi Bayezid ile arasının açılmasına sebep oldu. Lala Mustafa Paşa önce Van, sonra Erzurum, Halep ve Şam valiliklerine atandı. Ardından İstanbul'a gelerek Vezir oldu ve divana girdi.
Bu sırada padişaha Kıbrıs'ın fethedilmesi gerektiğini kabul ettirdi. Kendisi de Serdar-ı Ekremliğe atandı. Bir yıl süren savaş sonunda Kıbrıs, 1570 yılında fethedildi. Açılan İran seferi dolayısıyla Erzurum kuvvetleri serdarlığına atandı. 1578 yılında İran ordusunu bozarak Tiflis'e girdi. Gürcistan ve Şirvan'ı aldı.
1580 yılına kadar doğuda kalan Lala Mustafa Paşa, Sokullu Mehmed Paşa'nın ölümü üzerine azledilerek İstanbul'a çağrıldı. İkinci Vezir olarak görevlendirilen Lala Mustafa Paşa, padişaha fikir vermek bakımından yardımcı oluyordu. Aynı yıl İstanbul'da vefat etti.