Veli Paşa, Ali Paşa nın oğludur. Yanina valiliği (paşalığı) yapmıştır. Osmanlı komutanı olarak Souliotes, Yedi Ada Cumhuriyeti ve Sırp isyancılara karşı mücadele etti.
1803'te babası orduyla beraber onu Souliotes ile savaşmaya gönderdi. 1806 yılında, Osmanlılar ve Ruslar arasındaki yeni çatışmanın ardından Veli Paşa, Yedi Ada Cumhuriyeti 'ne saldırmak için gönderildi. Bu saldırılarda Veli Paşa Vonitsa, Preveze ve Butrint'i ele geçirdi. Ali Paşa, komşusu İbrahim Paşa'nın kızıyla Veli Paşa ile evlendirdi. Veli Paşa, Smederevo ( İlk Sırp İsyanı ) sancağında Sırp isyancılarını bastırmak için gönderilmiştir.
