Kavalalı Mehmet Ali Paşa'nın himayesinde Mısır'da yetişmiş olup, Arnavut asıllıdır. Yunanistan'ın bağımsızlığı kazandığı 1820'li yıllarda Sisam, Sakız ve Girit gibi Ege Adaları'nda da Rumların bağlantılı olarak ayaklanmalarına hazırlıksız yakalanan Sultan 2. Mahmud'un fiilen bağımsız Mısır Hidivi Kavalalı Mehmet Ali Paşa'dan yardım istediği dönemde Girit ayaklanmasını bastırmış ve 1832'de Mısır idaresine sokulan Girit'e vali tayin edilmiştir. Valiliği 20 yıla yakın bir süre sürdüğü için "Giritli" lakabı ile anılır.
Girit'i idaresi esnasında temkinli ve İngilizler yakın bir politika izlemiştir. Bir açıdan adanın Müslüman toprak sahipleri ile yükselen Rum tacir sınıfı arasında sentez kurmaya çalıştığı yorumu getirilebilirse de, Rumlara karşı tavizkar politikaları ada Müslümanlarının tepkileri ile de karşılaşmıştır. Bir Rum papazın kızı ile evlenmiş, karısı Hristiyan kalmiştır.
1840'da Britanya Başbakanı Lord Palmerston'un Girit'in Osmanlı idaresine geri dönmesi yönünde yaptığı baskı esnasında, bir süre için, yarı-bağımsız bir Girit'in prensi olma denemesinde bulunmuştur. Ancak belirsiz siyasi ortamı fırsat bilen Rumlar ayaklanmışlar, ve bu küçük çaplı isyan Britanya-Osmanlı donanmalarının müdahalesi ile sona erdirilmiştir. Girit böylece 1840'da Osmanlı Devleti bünyesine geri dönmüş, Giritli Mustafa Naili Paşa da vali olarak muhafaza edilmiştir. Valiliği İstanbul'a çağırıldığı 1851 yılına kadar sürmüştür. İstanbul'da da, ilerlemiş yaşına rağmen, kariyerini sürdürmüş ve sadrazamlığa kadar yükselmiştir.
Sadrazamlık dönemleri Kırım Savaşı'nın hemen öncesine ve ikinci dönemi de bir süre sonrasına denk gelmiş, gündemini Rusya ile ilişkiler meşgul etmiştir. Fransa’da imparatorluğunu ilan eden ve uluslararası ilişkilerdeki konumunu güçlendirmek isteyen III. Napoleon'un Osmanlı Devleti’nde yaşayan Katoliklerin himayelerini Fransa’ya veren 1740 tarihli antlaşmanın yeniden yürürlüğe girmesini istemesi üzerine, Rusya'nın da Osmanlı Ortodoksları için aynı hakları istediği ve katı bir asker ve koyu bir Ortodoks olan Prens Menşikov'u İstanbul’a olağanüstü yetkilerle elçi olarak yolladığı, bu sorunu kendi çıkarları için tehlike olarak gören İngiltere, Fransa ve Avusturya’nın Osmanlı Devleti'ne giderek artan destek verdiği Kırım Savaşı'na gidecek süreç esnasında ilk sadrazamlığına getirilmiş ve savaşın ilk döneminde bu görevi sürdürmüştür. Atanmasının nedeni Prens Menşikov'un taleplerinin kabul edilmemesi halinde İstanbul’dan ayrılacağı ültimatomunu vermesi ile, Prens'e sürekli direnen Sadrazam Damat Mehmet Ali Paşa ve Hariciye Nazırı Sadık Rıfat Paşa'nın görevlerinden alınmalarıdır. Böylece Sadrazamlığa Giritli Mustafa Naili Paşa, Hariciye Nazırlığına da Koca Mustafa Reşit Paşa atanmıştır. Ancak bu isim değişikliklerine rağmen Prens Menşikov yine de 27 Mayıs 1853’te İstanbul’dan elleri boş olarak ayrılmış ve Kırım Savaşı başlamıştır.