Əslən alban olub, 1798-ci ildə Kastoriya sancaqbəyliyinə bağlı Polyan kəndində doğulmuşdur. Atası İsmayıl bəy bu bölgənin yerli bəylərindən, dayısı Tahir Paşa isə Misir vilayəti hakimlərindən idi. Çox gənc yaşda Krit vilayətinə gedərək burada 30 ilə yaxın xidmət göstərmiş, bu səbəblə "Kritli" ləqəbiylə anılmışdır. Kiçik yaşlarında atası ilə birlikdə dayısı Tahir Paşanın yanına getmiş, dayısının, ardından isə atasının vəfatıyla vətənə qayıtmışdır. 1809-cu ildə yenidən getdiyi Misirdə digər dayısı Həsən Paşayla birlikdə Misir hakimi Kavalalı Mehmed Paşanın xidmətinə girmişdir. Vəhhabi üsyanı səbəbilə dayısı Həsən Paşa ilə birlikdə Hicaza yollandı və 5 ilə yaxın müddət burda hərbi təcrübə keçdi. 1821-ci ildə baş verən Krit üsyanı səbbəilə vəzifələndirilən Həsən Paşayla birlikdə bu dəfə də Kandiyəyə yollanan Mustafa Paşa Kavalalı Hüseyn bəylə birlikdə vilayətin idarəsini ələ aldı. Adanın idarəsinin Kavalalı Mehmed Paşaya verilməsi və Kavalalı Hüseyn bəyin İnəbaxdıya göndərilməsinin ardından 1826-cı ildə vilayətin bəylərbəyi olaraq təyin olundu. Dayısı Həsən Paşanın vəfatından sonra ona aid maaş, gəlir və mülklər Mustafa Paşaya ötürüldü. Bölgədəki ayaqlanmaarı yatıraraq iğtişaşların qarşısını aldı.

Bu vəzifədə ikən indiki Suriya ərazisindəki Dürzi üsyanının yatırılması məqsədilə 2 aprel 1838-ci ildə Dəməşqə göndərildi. Hələbdən gələn Kavalalı Mehmed Paşanın oğlu İbrahim Paşayla üsyanı yatırdıqdan sonra Kritə geri döndü. Burada qazandığı hərbi uğuru və Kavalalı Mehmed Paşanın 1840 tarixli London konfransı nəticəsində Krit adası üzərindəki idarəetmə hüququnu itirməsinin ardından vəzirlik rütbəsi alaraq ömürlük Krit hakimliyində saxlanıldı (31 dekabr 1840). 1841-ci ilin fevralında yunan quldur dəstələrinin adaya olan hücumunun qarşısını aldı. 1842-ci ilin iyulunda icazəylə İstanbula gəldi və Sultan Əbdülməcid tərəfindən hədiyyələr aldı. 1 iyun 1850-ci ildə Aralıq dənizində səyahətə çıxan Sultan Əbdülməcidi Kritə dəvət etdi və o əsnada İmtiyaz nişanı ilə təltif olundu. Ömürlük Krit hakimi olmasına baxmyaraq 1851-ci ilin payızında İstanbula çağırıldı və Ədliyyə məclisinə üzv, ardından 7 mart 1852-ci ildə bu məclisin rəisliyinə gətirildi. Eyni ilin 21 iyul və 17 sentyabr tarixlərində 2 dəfə olmaqla Məcidi ordeniylə mükafatlandırıldı.

14 may 1853-cü ildə Kavalalı Mehmed Paşanın yerinə sədarətə gətirilsə də, o əsnada dövlət idarəsi xarici işlər naziri Mustafa Rəşid Paşanın əlində cəmlənmişdi. Mustafa Naili Paşanın bu vəziyyəti qəbul edə bilməməsi və ikili arasında yaranan nifaq səbəbilə 8 iyulda hər ikisi vəzifədən alındı və 2 gün sonra isə vəzifələrinə geri qaytarıldılar. Buna baxmayaraq ikili arasındakı münasibətlər düzəlmədi. Belə ki, xarici borclanma məsələsiylə bağlı 28 may 1854-cü ildə toplanan məclisdə Mustafa Naili Paşa "Sən mənim sədarətimə imkan vermirsən" demiş, qəzəblənən Mustafa Rəşid Paşa isə məclisi tərk etmişdir. Ehtimal olunur iki, bu məsələnin sultanın qulağına gedib çıxması nəticəsində ertəsi gün Mustafa Naili Paşa vəzifədən alındı. 2 illik səssizliyin ardından 1856-cı ilin dekabrında Ali məclis üzvlüyünə gətirildi.

Balkan yarımadasındakı problemlərlə bağlı Fransa və Rusiya ilə münasibətlər pisləşmiş, bu vəziyyətdə sədarətdən geri çəkilən Mustafa Rəşid Paşanın yerinə 6 avqust 1857-ci ildə ikinci dəfə sədarətə gətirilmişdir. Buna baxmayaraq bu sədarəti də qısa sürmüş, Fransa ilə yaranan siyasi gərginliyin aradan qalxması ilə 22 oktyabrda vəzifədən alınmışdır. Bu sədarəti əsnasında Mustafa Rəşid Paşayla barışmış, vəzifədən alındıqdan sonra 1858-ci ilin martında yenidən Ali məclis üzvlüyünə gətirilmişdir. 19 dekabr 1861-ci ildə Osmanlı nişanı ilə təltif edilmişdir.

1866-cı ilin avqustunda başlayan üsyanın ardından 28 avqustda Murassa Osmani nişanı ilə təltif edilərək hakim ünvanıyla yenidən Kritə göndərilsə də, hadisələrin qarşısını ala bilmədi. 1867-ci ilin martında paytaxta çağırıldı və məclis üzvlüyünə davam etdi. 1860-cı illərin sonlarında Hicaz və Yəmən arasındakı dağlıq bölgədə çıxan üsyanın yatırılmasında mühüm rol oynadı.

28 dekabr 1871-ci ildə vəfat edən Mustafa Naili Paşanın məzarı Fateh türbəsinin həyətindədir. Krım müharibəsi əsnasında aldığı İftixar nişanı ilə birlikdə İmtiyaz nişanı, Məcidi nişanı, Murassa Osmani nişanı və Krit medallarının sahibi idi. Övladlarından Vəliüddin Rifat Paşa Paris səfiri, Bursa və Krit hakimi olaraq xidmət etmiş, digər oğulları Hilmi Paşa, Hüseyn Paşa, Mehmed bəy, Rauf bəy və Əli Qalib bəy müxtəlif hərbi və mülki vəzifələrdə çalışmışdır. Mir’ât-ı Şuûnât adlı əsərin yazarı olan Mehmed Məmduh Paşa isə onun kürəkənidir.

• Ahmed Rifat, Verdü’l-Hadâik, İstanbul 1283, s. 52–57;
• Cevdet, Tezâkir, I, 17;
• Sicill-i Osmânî, IV, 480–481;
• İbnülemin, Son Sadrıazamlar, I, 74–82;
• Gövsa, Türk Meşhurları, s. 265;
• Danişmend, Kronoloji2, V, 80–81;
• İsmet Parmaksızoğlu, "Naili Mustafa Paşa", TA, XXV, 80;