Bosnalı Hırvat asıllıdır. Devşirme olarak Enderun mektebine girmiş, oradan çıkmasından sonra çeşitli saray hizmetinde bulunmuştur. Sonra saraydan çıkıp diğer devlet işleri ile vazife aldı. 1554'de Mısır valisi olan Mahmud Paşa yanında kethuda olarak görev yaptı. 1554'de Mısır'da sancakbeyi oldu. 1571'de Koca Sinan Paşa ile birlikte Yemen Seferi'ne çıktı ve iki yıl kadar Yemen Beylerbeyi oldu. Sonra İstanbul'a döndü. Çok geçmeden Şarki Karahisar (Şebinkarahisar) Sancakbeyi olarak İstanbul'dan ayrıldı. Sonra Anadolu'da çeşitli yerlerde sancakbeyliği görevi yaptı. Bu arada üç defa da Diyarbakır Beylerbeyliği yaptı. Karaman Beylerbeyi iken eyalet askerinin başında olarak Özdemiroğlu Osman Paşa serdarlığı altında İran Seferi'ne katıldı. 1585'de bu seferde iken atı sürçüp bir çukura düşmesi sonucu İranlılara esir düştü. İngiliz Elçisi Lallo hatıralarında Kuyucu Murat Paşa'nın üç yıl savaş esiri olarak İran Şahı yanında kaldığını belirtmektedir.
Esaretten kurtulduktan sonra Kıbrıs Beylerbeyliği görevine atandı. Buradan Avusturya Seferi'ne katılmak üzere ayrıldı ve uzun yıllar Macaristan cephesinde askeri hizmet gördü. 1606'da ran'a seferine serdar tayin edilen Serdar-i Ekrem ve Sadrazam Sokolluzade Lala Mehmed Paşa Macaristan cephesinden ayrılması gerekince, sadrazam Kuyucu Murat Pasa'yı Avusturya cephesi serdari olarak görevlendirdi. Sokolluzade Lala Mehmed Paşa tarafından Avusturyalılar ile yapılmaya başlanan ve 11 Kasım 1606'da Zitvatorok Antlaşması ile sona erecek olan barış müzakereleri Kuyucu Murat Paşa tarafından devam ettirildi. Bu barış antlaşmasının Osmanlı Devleti'nin imzalandığı en kârli antlaşma olduğu kabul edilmektedir.
Bu antlaşma müzakereleri sona erip antlaşma imzalandıktan sonra Kuyucu Murat Paşa Belgrad'a döndüğü zaman, sadrazam olan Boşnak Derviş Mehmed Paşa'nın 9 Aralık 1606'da azledilip idam edildiği haberi orayaulaştı. Yerine, Şeyhülislam Sunullah Efendi'nin tavsiyelerine uyan Sultan I. Ahmet Kuyucu Murat Paşa'yı sadrazam olarak tayin etti. Mühr-ü hümayun 11 Aralık 1606'da Belgrad'da Kuyucu Murat Paşa'ya erişti.
Kuyucu Murat Paşa sadrazamalık döneminde Anadolu'da çıkan Celalı Ayaklanması'na karışan isyancıları idam ettirmesi ile tanınmaktadır. 1607 ilkbaharından 1608 sonlarına kadar Kuyucu Murat Paşa, Anadolu'da sefer yapıp Anadolu'yu Celalileri temizleme operasyonları yapmıştır. Bu arada Canbolatoğlu, Kalenderoğlu, Kara Said gibi büyük isim yapmış Celalı eşkiyasını tepelemiştir. Yaşı epeyce ileri olduğu için Anadolu'nun birçok yöresini kapsayan bu kampanyasında uzun zaman at üzerinde bulunması yaşına göre zor olduğu için kendini ata bağlattırdığı bildirilmektedir. "Kuyucu" lakabını öldürttüğü Celali isyancılarının ve onların destekçilerini ölü ve diri derin kuyulara gömdürmesi nedeni ile almıştır. Yıllarca Anadolu'da öldürttüğü kişilerin kellelerinden yaptırdığı piramitler bir korku hikayesi olarak anlatıldı. Çok soğukkanlı, çok gaddar ve amansız olduğu bilinmektedir. Yaşa başa bakmadan; erkek, kadın, Celali eşkiyasına destek verdiğini kabul edilen herkesi, özellikle Doğu Anadolu'da bulunan Alevi vatandaşları, öldürtmeyi amaç edinmişti. Bu kampanya sırasında Anadolu'da öldürttüğü kişi sayısının 30.000 kişiyi geçtiği bildirilmektedir..
İstanbul'a döndüğünde 1609 başında İran hükümdarı Şah Abbas'a karşı yeni bir İran seferi hazırlıkları başlamıştı. Sultan'la gizli görüşmelerden sonra Kuyucu Murad Paşa sefer serdarı tayin edildi. Sefere çıkmadan ordunun hazırlanması için Sadrazam Kuyucu Murad Paşa Üsküdar'da ordugahta kaldı ve oradan sefer hazırlıklarını idare etti. Celalileri bastırma operarasyonuna da hala devam edip önceki yıl yakalayamadığı birçok Celali başbuğunu rütbe ve görev verme sözüyle kandırıp Üsküdar'a getirip birer ikişer idam ettirdi.
Bu seferde Safavi Şah Abbas hiçbir önemli faaliyette bulunmadı ve İranlılar 1604'den beri ellerine geçirdikleri Revan, Tebriz ve Gürcistan ve yörelerindeki kazançlarını konsolide etmeye koyuldular ve Osmanlı ordusu bu yöreleri geri alamadı. 1610'dan itibaren İran elçileri ile sulh müzakereleri başlayıp ilerledi. Yaşı epeyce ileri olan serdar Kuyucu Murat Paşa 15 Ağustos1611'de ordugâhı bulunan Diyarbakır'da vefat etti. Cesedi İstanbul'a nakledilerek Vezneciler medresesi yanında bulunan türbesine gömüldü.