Kökeni ve hayatı hakkında devrin kaynaklarında çok az bilgi vardır. Kemalpaşazâde, onun İstanbul’un fethinde esir düşen Rumlar’dan olup gılman olarak saray hizmetine alındığını yazar. Bu bilgi dolaylı da olsa Mehmed Paşa’nın çağdaşı Âşıkpaşazâde’nin tarihinde de yer alır ve onun Michael Kritovulos’un sözünü ettiği eşraf çocuklarının en iyilerinden biri olduğunu düşündürür. Franz Babinger’in Mehmed Paşa’nın menşeinin Anadolu veya Dimetoka olabileceği iddiası mevcut kaynaklarla desteklenmemektedir. Muhtemelen Enderun Mektebi’nde yetiştirilerek yükselmiş ve bu arada Fâtih Sultan Mehmed’in güvenini kazanmıştır. 870’te (1466) II. Mehmed’in Arnavutluk seferinin hemen ardından ikinci vezirlik makamına getirildi.
Kaynaklara göre, Fâtih Sultan Mehmed’in 872’deki (1468) Karaman seferinde Mehmed Paşa ile Vezîriâzam Mahmud Paşa arasında bulunan gizli rekabet ve çekişme su yüzüne çıktı. Mehmed Paşa, Mahmud Paşa’nın İstanbul’u ihya ve iskân etmek için Lârende (Karaman) ve Konya’dan birkaç yüz hânenin sürgün edilmesinde yeterince sert davranmadığı suçlamasında bulundu. Nitekim kısa bir süre sonra Mahmud Paşa’nın yerine sürgün işini acımasızca tamamladı ve Mevlânâ Celâleddîn-i Rûmî torunlarından olan Emîr Ali Çelebi’yi de İstanbul’a gönderileceklerin arasına soktu. 873’te (1468-69) Mahmud Paşa’nın sadrazamlıktan azlinin ardından Rum Mehmed Paşa’nın bu makama getirildiğine dair iddialara rağmen bazı kayıtlar, Mahmud Paşa’nın sadrazamlıktaki halefi olarak Rum Mehmed’e değil İshak Paşa’ya işaret etmektedir. Rum Mehmed Paşa’ya karşı aşırı derecede ön yargılı olan Âşıkpaşazâde’nin belirttiği gibi Mehmed Paşa, Karaman’daki tehcir harekâtının sonunda Keblü oğlu Muhyiddin’in yerine Mevlânâ Vildan’ı kazaskerliğe getirtmeyi başardı. Mehmed Paşa 874’te (1469-70) yine Karaman’a gönderilip Mut Kalesi’ni tahrip ederek seferini başarıyla tamamladı.
875’te (1470) Mehmed Paşa, Eğriboz fethine önemli katkıda bulundu ve aynı yılın sonbaharında tekrar Karaman’a gönderilince Lârende ve Ereğli’yi tahrip ederek Toros dağlarının kuzeyini ele geçirdi. Güneye Varsaklar’a karşı yürürken Varsaklı Uyuz Bey’in kurduğu pusuya düştü ve kendini zor kurtardı. Âşıkpaşazâde ve Neşrî’ye göre Mehmed Paşa bu arada Alanya’yı fethetmekten vazgeçti. Bunun sebebi Alâiye Beyi Kılıcarslan’ın kız kardeşiyle evli olmasıydı. 1471’de İshak Paşa, Ankara’ya kadar yürüyen Karamanoğlu Kasım Bey’e karşı başarılı olamadığından azledilince Mehmed Paşa sadrazamlığa yükseldi. Bu dönemde kitâbesinden anlaşıldığı üzere (876/1471-72) Üsküdar’daki cami, medrese, hamam, imaret ve türbeden ibaret külliyesini tamamladı. Burasının vakıf gelirleri arasında Mehmed Paşa’nın Manisa’da yaptırdığı bir bedesten de bulunuyordu.
877 (1472) senesi yazında Karamanoğulları’nı himayesi altına almış olan Akkoyunlu Hükümdarı Uzun Hasan’ın bir ordusunun Tokat’a ilerleyip şehri zaptederek yağma ettiği haberi üzerine Mehmed Paşa makamını yitirdi. Bu tarihte idam edildiği yolunda görüşler varsa da 879 (1474) yılında Cem Sultan’ın atabeyi olarak Karaman’da bulunduğuna dair bir kayıt mevcuttur. Halil İnalcık, İdrîs-i Bitlisî’nin Heşt Bihişt’ine dayanarak Mehmed Paşa’nın Varsaklar’a karşı başarısız olan seferinin bu tarihte yapıldığını ve paşanın azli ve idamı ile sonuçlandığını yazar. Onun hakkında ağır tenkitlerde bulunan Âşıkpaşazâde, “İt gibi boğdular” derken tarih vermez. Kemalpaşazâde ise yine tarih belirtmeden Mehmed Paşa’nın idamını Karamânî Mehmed Paşa’nın nifakına bağlar. Diğer taraftan genişletilmiş Oruç Bey tarihinde Rum Mehmed Paşa, Gedik Ahmed Paşa’nın damadı olarak gösterilir. 885 (1480) gibi geç bir tarihte Anadolu beylerbeyi diye zikredilirse de bu kaydın doğruluğunu destekleyecek başka bilgi yoktur.
Osmanlı tarihçileri, Âşıkpaşazâde’ye dayanarak genellikle Mehmed Paşa hakkında olumsuz ifadeler kullanmakta, özellikle İstanbul’da fetihten sonra yeni getirtilenlere ve ulemâya tahsis edilen evlerden kira alınması kararındaki rolü üzerinde durmaktadır. Bunun dışında Âşıkpaşazâde onun vezirliği sırasında ulemâya ve fakirlere dağıtılması gereken in‘âmları, elbiseleri ve kumaşları verdirmediğini yazar. Rum Mehmed Paşa’nın İstanbul’daki eserleri yanında Tire’de cami, han ve türbe yaptırdığı bilinmektedir.