Bosniya yaxınlığındakı Yaytse şəhərində dünyaya gəlmişdir. Məşhur Osmanlı sədrəzəmi Sokullu Mehmed Paşanın uzaq qohumudur. Kiçik yaşlarında Topqapı Sarayına gətirildi və Əndəruna daxil oldu. Sultan I Əhmədin şahzadəlik dönəmində lələsi olmuş, bu səbəbdən lələ ünvanı almışdır. 24 fevral 1591 tarixində yeniçəri ağası seçilmiş, bu vəzifədə ikən 1594-cü ildə Avstriya səfərinə çıxdı. 1594-cü ilin avqust ayında Qaraman bəylərbəyi, 26 sentyabr 1594 tarixində isə Anadolu bəylərbəyi təyin edildi. Bir müddət sonra Rumeli bəylərbəyi seçildi. Bu vəzifədə ikən Esterqon qalası Avstriya ordusu tərəfindən mühasirəyə alındı. 2 avqust 1595 tarixində başlayan mühasirə 28 gün davam etdi. Lələ Mehmed Paşanın qapı xalqından olan İbrahim Peçəvi, bu mühasirəni öz xatirələrində ən kiçik xırdalığına qədər qeyd etmişdir. Lələ Mehmed Paşa 30 avqust 1595 taixində qalanı təslim etdi.

1596 tarixində vəzirlik rütbəsi verildi. Sədrəzəm Yemişçi Həsən Paşanın 1601-ci ildə çıxdığı Avstriya səfərindən sonra Macarıstan sərdarı təyin olundu. 1596 tarixindəki Xaçoba müharibəsinə qatıldı. 17 avqust 1598 tarixində yenidən Rumeli bəylərbəyi təyin olundu. 1599-cu ilin noyabr ayında Budin bəylərbəyi seçildi. Malqoç Yavuz Əli Paşanın vəfatının ardından 1604-cü ildə sədarətə gətirildi.

Sədrəzəmliyinin ilk ilində Vaç və Hatvan qalalarını aldı. 10 il əvvəl təslim etdiyi Esterqon qalasını 29 avqust 1605 tarixində mühasirəyə aldı və 3 oktyabr tarixində ələ keçirdi. Qala ikinci fəthinin ardından 1683 tarixinə qədər Osmanlı mülkü sayıldı. Macar əsilzadəsi olan İstvan Bocskai`nin macar kralı olmasını təmin etdi. I Əhmədin təmsilçisi olaraq ona qılınc və tac geydirdi.

Avstriya ilə sülh danışıqları səbəbilə 1606-cı ilin may ayında paytaxta geri döndü. Ancaq Lələ Mehmed Paşanı özünə rəqib olaraq görən Dərviş Paşa sədrəzəmi paytaxtdan uzaqlaşdırmaq niyyətində idi. Bu məqsədlə sədrəzəmin Səfəvi cəbhəsinə yollanması üçün gənc padşaha təkidlər edirdi. Nəhayət, I Əhməd lələsi olan Lələ Mehmed Paşanı Səfəvi cəbhəsinə göndərmək üzrə qərar verdi. Ancaq Lələ Mehmed Paşanın cəbhəyə getmək istəməməsi səbəbilə padşahla münasibətləri pozulmuş, I Əhməd hətta öz lələsini edamla qorxutmuşdur. Bu olanları qəbul edə bilməyən Lələ Mehmed Paşa bir müddət sonra iflic keçirərək vəfat etdi. Məzarı Əyyub Sultan məscidindəki Sokullu Mehmed Paşa türbəsinə dəfn edilmişdir.