Veli Mahmud Paşa
Birinci sadrazamlığı

Veli Mahmud Paşa'nın ne zaman ilk defa ne zaman ve nasıl sadrazam tayin edildiği hakkında bazı bilgiler mevcuttur ve bu bilgiler ışığında iki farklı yaklaşım bulunmaktadır.
Buna göre bazı tarihçiler 1 Haziran 1453'te II. Mehmed'in tecrübeli sadrazam (2.) Çandarlı Halil Paşa'yı idam ettirip yerine Veli Mahmud Paşa'yı birinci defa başvezir yaptığını bildirirler.
Fakat diğer tarihçilerse bunu kabul etmemektedir. 1453'te Çandarlı Halil Paşa'nın idamından sonra Zağanos Mehmed Paşa'nın sadrazamlığa getirildiğini ve ancak onun 1456 yılında Belgrad muharebesindeki başarısızlığı dolayısıyla görevden azledilmesi ile 1456'da ikinci vezir olan Veli Mahmud Paşa'nın sadrazam olduğunu bildirirler.
Mahmud Paşa sadrazamlığı sırasında Fatih Sultan Mehmed stratejisini çizdiği Balkan egemenliğini ele alma sorunları ile yakından ilgilendi. 1456'da Zağanos Paşa'nın Macarlara karşı Belgrat seferindeki  başarısızlığından sonra Mahmud Paşa önce Sırbistan sorunu ile ilgilenmek zorunda kaldı.
1458'de Sırp Despotu Brankoviç ölmesi ile Osmanlı Devleti ile Macar Krallığı arasında mücadele yeniden canlandı. Sırp Despotluğu içinde, bir grup Macar tarafını ve diğer bir grup Osmanlı tarafını tutmaktaydı. Mahmud Pasa Sırp meselesinin halledilmesiyle görevlendirildi. Kendi parasıyla teçhiz ettiği Rumeli askerine Anadolu askerini ve padişahın yolladığı 1000 yeniçeriyi katarak 1458'de Sırbistan Seferi'ne girişti. 1458'de Mahmud Paşa Sırbistan Seferine çıktı. Reşav, Kuruca, Ostrovica, Durnik  ve Güvercinlik (Golubac) kalelerini ele geçirdi. Ama Semendire'ye ele geçiremedi. Sırp Despotluğu böylece tamamıyla işgal edilerek Osmanlı Devleti'ne ilhak edildi. Temmuz 1458) Macaristan'a akıncılar gönderdi. Ardından Üsküp'te bulunan padişahın yanına döndü.
1458'de Mora Despotluğu içinde taht kavgası çıktı. Despotluk iddiacılarından Thomas Osmanlı Devleti himayesini istedi ve rakibi Demetrios Venediklilerin desteğini almıştı. Önce 1458'de Fatih Mora seferine çıktı. 1460'ta ise Fâtih'le birlikte İkinci Mora Seferine çıkarak, despotluk başkenti Mistra’nın fethinde bulundu. Fakat Venedikliler Nauplia, Koron, Modon vb. kaleleri ellerinde tuttular.
Sonra Anadolu'da bulunan eski Bizans ve İtalyan Ceneviz deniz koloni kalıntılarına karşı seferlere başladı. Mahmud Paşa, Fâtih ile birlikte yaptığı seferlerde Amasra 1459'da, Sinop ve Trabzon 1461'de Osmanlı Devleti eline geçirilmesini sağladı. Böylece 1204'ten itibaren hükûmet süren Trabzon Rum Devleti'de ortadan kaldırıldı.
1462'de Eflak Voyvodası, "Kazıklı Voyvoda" olarak da anılan, III. Vlad'ın gönderilen Osmanlı elçisi Hamza Paşa'yı kazığa çaktırıp idam ettirmesi dolayısı ile Mahmud Paşa bir Eflak seferine çıktı. Târgovişte gece baskını öncesinde II. Mehmed tarafından gönderildiği seferde III. Vlad tarafından bozguna uğratıldı.
Eflak Seferi'ni takiben o yıl 1462'de Midilli adasının fethi için 100 kadar gemiden oluşan Osmanlı filosu ile sefere gönderildi. Bu adanın ana şehri  27 gün suren bir kuşatmadan ve donanmanın devamlı bombardımanından sonra 19 Eylül 1462'da teslim oldu. Dük esir alındı ve adaya bir Osmanlı yöneticisi atandı.
1463'te Mahmud Paşa yine sultan II. Mehmed ile birlikte Bosna Seferi'ne geçti. Son Bosna Kralı olan Stjepan Tomašević başkenti Bobavec'den, Yayce'ye ve sonra da Kluj'a kaçtı ise de orada yakalanıp Mayıs sonunda idam edildi. Bosna krallık hanedanı ailesi dağıtılıp Bosna bir Osmanlı Beylerbeyliği olarak ilhak edildi. Hersek'te de hükümdarlık iddia eden hanedan mensupları dağıtıldı.
Bu seferden dönmekte iken Venediklilerin Mora ve havalisinde çıkardıkları sorunları etkisiz hale getirmekle de uğraşıp sahil dışındaki bölgelerden Venediklileri uzaklaştırdı.
Bosna ve Hersek'te bu gelişmelere karşılık Macar Krallığı ile ciddi bir savaş durumu ortaya çıktı. Macaristan, Venedik ve Arnavutluk'ta bağımsız olan İskender Bey bir ittifaka girdiler. Bu ittifakı Papa II. Pius bir Haçlı Seferi haline getirmeye çalışmakta idi. Diğer taraftan bu Haçlı ittifakı Doğu Anadolu'da hakim olan Akkoyunlular hükümdarı Uzun Hasan ile elçiler göndererek anlaşmaya girişmeye çalıştı.
Macar Kralı Matyas Corvinus Aralık 1463'te  Bosna'da yeni yapılmakta olan Yayçe kalesine hücumu üzerine, 1464'te Mahmud Paşa Bosna ve Macaristan üzerine sefere çıktı. Osmanlı ordusunun Bosna'ya gelmesiyle Macarlar kaçtı. Pek çok ganimet ve esirin ele geçmesini sağladı.
İlk sadrazamlığı Rum Mehmed Paşa'nın, Veli Mahmut Paşa'yı Fatih Sultan Mehmed'e kötülemesi yüzünden sonlanmıştır. Bu kötüleme Karamanlılar topraklarından gelen Türk muhacirlerin 1466 başlarında İstanbul'a yerleştirilmeleri sırasında Veli Mahmut Paşa'nın aldığı rüşvet ve kendini zengin etmek için giriştiği icraatlardan dolayı olduğu bildirilmektedir. Görevden alındıktan bir süre sonra Kaptan-ı derya olarak donanmanın başına getirildi.