Osmanlı sadrâzamlarından. 1798 yılında Manastır vilâyetinin Polyan köyünde doğdu. Mısır’da görevli olan dayısı Tâhir Paşanın mahiyetinde, çocuk yaşından îtibâren silahşor olarak yetiştirildi. Kavalalı Mehmed Ali Paşanın hizmetinde bulunarak Vehhâbîlere karşı olan harekâtta görev aldı ve beş yıl Mekke’de kaldı. Diğer dayısı Hasan Paşa ile birlikte 1821 Girit İsyânını bastırmak için Kandiye’ye gitti. Genç yaşında Mîrimîrânlık rütbesi verildikten sonra 1826’da Kandiye Muhâfızı oldu. 1838’de Girit İsyânını bastırmak için Kandiye’ye gitti. Lübnan’da kargaşalığı bastırmak için Şam’a geldi ve İbrâhim Paşanın kuvvetlerine askerleriyle birlikte katıldı. Dürzî ve Marûnîlerin çıkardığı ayaklanmanın bastırılmasında yararlılıkları görüldü. Sultan Abdülmecid’in Adalar Denizi gezisine katılarak pâdişâhı Girit’te konağında misâfir etti. 1851’de Meclis-i vâlâ üyeliğine, sonra da başkanlığına getirildi. 1853’te Vezir-i âzam oldu. Bir sene bu görevde bulunduktan sonra sadâretten ayrıldı ve 1857’de ikinci defâ Sadrâzam oldu. Üç aylık görevinden sonra Girit İsyânını bastırmakla vazifelendirildi. Oradan bir müddet sonra çağrılarak Mecâlis-i âliyeye memur edildi. 29 Aralık 1871’de ölen Nâilî Mustafa Paşa, Fâtih Türbesi civârında defnedildi. Devletine sâdık, sergerdelikten yetişme silahşor meziyetli olan Paşa, yabancı devletlerin Osmanlıyı parçalamak istedikleri Tanzimat devri politikasında kendini hissettiremedi.