Əslinin nə olduğu haqqında tarixçilər arasında böyük müzakirələr ortaya çıxmışdır. Zamanında hazırlanmış olan Ecthesis Chronica və Historia Patriarchia adlı salnamələrə görə Serb əsillidir və bir çox müasir tarixçi də bunu qəbul edirlər. Aşıq Çələbi "Təzkirə" si və Daşkörpülüzadə tarixinə görə əsli xorvatdır və buna qatılan müasir xarici tarixçilər də var. 1420'də Balkanların orta kəsimində, bu gün Kosovanın qərbində yerləşən Nobırda adlı bir qəsəbədə anadan olmuşdur.1427'də Osmanlıların Serbiya Despotluğu nu ələ keçirdikləri ildə gənc olaraq Osmanlılara əsir düşmüş və dəvşirmə yazılaraq Ədirnəyə göndərilmişdir. Dövrün yunan tarixçisi Laonikos Halkokondiles onun anası ilə Nobırdadan Səməndərəyə qaçmaqda ikən II. Muradın əsgərləri tərəfindən əsir alındığını qeyd edir. Dəvşirmə olaraq Ədirnədəki saray əndərun məktəbində təhsil almışdır. Təhsil həyatı bitdikdən sonra yeniçəri zabiti olaraq hərbiyə ilə məşğul olmuşdur. 1453 İstanbulun fəthi əsnasında yeniçəri ağası olaraq hərbi uğurlar göstərmişdir. 1454'də Rumeli Bəylərbəyi olmuşdur. Vəli Mahmud Paşa bu vəzifəni birinci sədrəzəm olduqdan sonra da yerinə yetirməyə davam etmişdir. Birinci dəfə sədrəzəmlikdən ayrılana qədər sədrəzəmliklə Rumeli Bəylərbəyi vəzifələrini birlikdə üzərinə götürmüşdür.

Vəli Mahmud Paşanın nə zaman ilk dəfə sədrəzəm təyin edildiyi haqqında tam məlumatımız yoxdur.

Bəzi tarixçilər 1 iyun 1453-cü ildə II. Mehmedin təcrübəli sədrəzəm Çandarlı (2.) Xəlil Paşanı edam etdirib yerinə Vəli Mahmud Paşanı birinci dəfə sədrəzəm seçdiyini bildirirlər.

Lakin çox önəmli tarixçilər bunu qəbul etmirlər. 1453-cü ildə Çandarlı Xəlil Paşanın edamından sonra Zağanos Paşanın sədrəzəmliyə gətirildiyini və onun 1456-ci ildə Belqrad müharibəsindəki müvəffəqiyyətsizliyi səbəbindən vəzifədən azad edilməsi ilə 1456'da ikinci vəzir olan Vəli Mahmud Paşanın sədrəzəm olduğunu bildirirlər.

1456'da Zağanos Paşa macarlara qarşı Belqrad səfərindəki uğursuzluğundan sonra Mahmud Paşa əvvəl Serbiya münaqişəsi ilə məşğul olmaq məcburiyyətində qaldı. 1458'də Serb despotu Brankoviçin ölməsi ilə Osmanlı Dövləti ilə Macarıstan Krallığı arasında mübarizə yenidən canlandı. Serb Despotluğu daxilində, bir qrup Macarıstan tərəfini və digər bir qrup Osmanlı tərəfini tutmuşdu. Mahmud Paşa 1459'da Serbiya Səfərinə çıxdı. Reşav, Kuruca, Ostçovica və Durnik qalalarını işğal etdi və despotluq beləcə bütövlükdə işğal edilərək Osmanlı Dövlətinə ilhaq edildi.

1458'də Mora Despotluğu daxilində taxt davası çıxdı. Despotluq namizədlərindən Thomas Osmanlı Dövləti himayəsini istədi və rəqibi Demetrios venesiyalıların dəstəyini almışdı. Əvvəlcə 1458'də Fateh Mora səfərinə çıxdı. 1460'da isə Mahmud Paşa Fatehlə birlikdə İkinci Mora Səfərinə çıxaraq, despotluğun paytaxtı Mistora'nın fəthini reallaşdırdı. Lakin venesiyalılar Nauplia, Koron, Modon və s qalaları ələ keçirdilər.

Sonra Anadoluda olan keçmiş Bizans və İtalyan Genuya dəniz müstəmləkə qalıqlarına qarşı səfərlərə başladı. Mahmud Paşa Fateh ilə birlikdə çıxdığı səfərlərdə Amasra 1459'da, Sinop və Trabzon 1461-ci ildə Osmanlı Dövləti əlinə keçirilməsini təmin etdi. Beləcə 1204'dən etibarən hökm sürən Trabzon-Yunan Dövləti də ortadan qaldırıldı.

1462'də Əflaq Voyvodası, "Drakula" olaraq da tanınan, III. Vladın göndərilən Osmanlı elçisi Həmzə Paşanı dirəyə asdırıb edam etdirməsi səbəbi ilə Mahmud Paşa bir Əflaq səfərinə çıxdı. Targoviste gecə basqınından əvvəl II. Mehmed tərəfindən göndərildiyi səfərdə III. Vlad tərəfindən məğlubiyyətə uğradılır.

1463'də Mahmud Paşa Bosniya Səfərinə keçdi. Son Bosniya Kralı olan Stjepan Tomasevic paytaxtı Bobavec'dən, Yayce'yə və sonra da Kluj'a qaçdı isə də orada tutulub May sonunda edam edildi. Bosniya krallıq xanədanı paylandı, Bosniya bir Osmanlı Bəylərbəyliyi olaraq ilhaq edildi. Herseqovinada da hökmdarlıq iddia edən xanədan mənsubları dağıdıldı.

Bosniya və Herseqovinada bu hadisələrə görə Macarıstan Krallığı ilə ciddi bir döyüş vəziyyəti ortaya çıxdı. Macarıstan, Venesiya və Albaniyada müstəqil olan İskəndər bəy bir ittifaqa girdilər. Bu ittifaqı Papa II. Pius bir Səlib yürüşü halına gətirməyə çalışmaqda idi. Digər tərəfdən bu Səlib ittifaqı Şərqi Anadoluda hakim olan Ağqoyunluların hakimi Uzun Həsən ilə elçilər göndərərək razılaşmağa çalışdı.

Macar Kralı Matthias Corvinusun dekabr 1463'də Bosniyada yeni tikilməkdə olan Yaycı qapısına hücumu üzərinə, 1464 də Mahmud Paşa Bosniya və Macarıstan üzərinə səfərə çıxdı. Osmanlı ordusunun Bosniyaya gəlməsiylə Macarlar qaçdı. Bir çox qənimət və əsirin ələ keçməsini təmin etdi.

İlk sədrəzəmliyi Yunan Mehmed Paşanın, Vəli Mahmud Paşanı Fateh Sultan Mehmedə pisləməsi səbəbindən sonlanmışdır. Bu pisləmə Qaramanlılar torpaqlarından gələn Türk mühacirlərin 1466 əvvəllərində İstanbula yerləşdirilmələri əsnasında Vəli Mahmud Paşanın aldığı rüşvət və özünü zəngin etmək üçün girişdiyi icraatlardan ötrü olduğu bildirilməkdədir. Vəzifədən alındıqdan bir müddət sonra Kaptan-ı Dərya olaraq donanmanın başına gətirildi.

Kaptan-i Dəryalığı əsnasında Əyriboğaz səfəri üçün donanmanı təşkil etməklə vəzifələndirildi. Əyriboğaz adası və qalasının mühasirəsində donanma ilə və öz birlikləri ilə böyük faydalılıqlar göstərib, padşahla birlikdə qalanın mühasirəsində və mühasirənin davam etdirilməsində təkid etdi. Venesiya donanmasının mühasirəni aşıb qalaya kömək etməsinə mane oldu və nəticədə qala düşdü. Bu müvəffəqiyyətləri və digər xidmətləri nəticəsində İshaq Paşanın ardından, ikinci dəfə sədrəzəmliyə gətirildi.

1472-ci ildə 2. dəfə sədrəzəmliyə gətirilən Vəli Mahmud Paşa padşahla birlikdə Uzun Həsənə qarşı səfərə çıxmış və bu səfərdə xüsusilə strateji baxımdan pis bir mövqedə başlayan Osmanlı qüvvələrinin buna baxmayaraq silah üstünlüyü və müvəffəqiyyətli taktikalarla Otluqbeli Müharibəsini qazanmasında böyük rol oynayanlardan biri olmuşdur.

Ancaq ikinci sədrəzəmliyində xalq tərəfindən sevilməsinə baxmayaraq II. Mehmed ilə əlaqələri ilk sədrəzəmliyi kimi yaxşı olmamışdır. Bunun səbəbi Şahzadə Mustafa və saraydakı bir sıra dövlət adamları ilə daxil olduğu çəkişmələrdir. Bunun nəticəsində 1474-cü ildə II. Mehmed tərəfindən edam etdirilmişdir. Edam səbəbi isə tam bilinmir.