Він народився під ім'ям Баїца — Байо Ненадіч[5], 1505 р поруч з містом Рудо в сербському селі Соколовичі в Герцеговині, через що отримав прізвисько «Соколлу». Його батько — Дмитро — був православним сербом[6]. У дитинстві майбутній візир отримав освіту в монастирі Мілешева.
У дитинстві потрапив в Едірне, де згодом був навернутий в іслам, отримав ім'я Мехмед і протягом багатьох років служив у корпусі яничарів. Згодом потрапив в імперську канцелярію, де перебував до 1535 року, аж поки в Багдаді під час перського походу султана Сулеймана внаслідок звинувачень у корупції і хабарництві (не без допомоги Паргали Ібрагім-паші) не був страчений Іскандер Челебі — головний скарбник імперії.
Початок кар'єри
Як воїн він відзначився в битві при Могачі в 1526 році, потім брав участь в облозі Відня (1529 г.), яка, однак, не виявилася успішною. У 1541 році Мехмед Соколлу став начальником придворної варти самого султана Сулеймана Пишного, згодом зблизившись з ним.
Капудан-паша (1546—1551)
У 1546 році від хвороби помер знаменитий капудан-паша (головний адмірал) османського флоту Хайр-ад-Дін Барбаросса. Його наступником був призначений Соколлу, хоча розглядалася також кандидатура Тургут-реїса. За п'ять років, що він провів на цій посаді, був організований ряд військових морських експедицій, в тому числі до морських фортець сучасного Триполі; також був значно збільшений арсенал корабельного озброєння.
Бейлербей Румелії (1551—1555)
У 1551 році був призначений бейлербеем (намісником) Румелії, однією з двох головних адміністративних провінцій (поряд з Анатолією). Ця посада відкривала Мехмеду-паші дорогу до Ради Дивану на посаду Візира.
На посту бейлербея він досить успішно вів військові дії проти Фердинанда I Габсбурга, ерцгерцога Австрії. У 1540 році після смерті угорського короля Яноша I Заполья, Фердинанд анексував його володіння (Східно-Угорське королівство). За терміновим наказом султана разом з 100-тисячною армією Соколлу Мехмед-паша вторгся в бунтівну Трансільванію і захопив 16 найбільших міст, в тому числі Бечей, Зренянин, Липова та інші. Повернувшись в Белград, Соколлу почав переговори з намісниками австрійського ерцгерцога на територіях Угорщини і Румунії, підконтрольних Габсбургам, однак після того як регент малолітнього князя Трансільванії і короля Угорщини Яноша II Сигізмунда Запольяі — Георг Мартінуцці був убитий в результаті замаху, Мехмед-паша в 1552 році знову рушив з військом, захопивши Тімішоару, Голоке, Ретшаг, Балашадьярмат, а також весь Сольнок і Банат.
Візир Османської імперії
Третій візир
Оцінивши навички та вміння Мехмеда-паші, Сулейман призначив його на посаду Третього Візира і дав йому місце в Раді Дивану. Бейлербеем Румелии став боснієць Перт-паша, давній друг і однодумець Мехмеда-паші. Після страти старшого сина султана, Шехзаде Мустафи, в Салоніках спалахнуло повстання лже-Мустафи, на придушення якого був спочатку відправлений Баязид. Соколлу Мехмед з десятитисячної армією, в числі яких було 3 тисячі яничар, жорстоко розправився з повсталими; лже-Мустафа був страчений.
Коли Кара Ахмед-паша, на той час великий візир, був звинувачений у хабарництві і потім страчений, на його місце вдруге був призначений Рустем-паша, який мав безліч ворогів серед пашів і беїв. Одним з них був старий Лала Мустафа-паша, вихователь третього сина Сулеймана I — Баязида. Після смерті Хюррем Султан — дружини султана, почалася міжусобна війна за владу між її синами. 1559 року Баязид, який зібрав величезне військо, вирушив у похід проти свого старшого брата, спадкоємця престолу — Селіма (пізніше Селім II). Мехмед-паша Соколлу разом з султанським військом вирушив до Коньї, де об'єднався з армією Лала Мустафи-паші. Баязид був розбитий чисельно переважаючими силами старшого брата, і втік до Персії. Соколлу Мехмед-паша залишився в Анатолії для переговорів з шахом Ірану Тахмаспа про екстрадицію бунтівника. Через два роки, в 1561 році, Баязид все ж був виданий за величезний викуп і страчений в Казвіні разом із п'ятьма його синами.
Другий візир
У 1561 році помер візир-і-азам Рустем-паша. На його місце, відповідно до ієрархією візирів, був призначений Семиз Алі-паша. Соколлу Мехмед, просунувшись по службових сходах, став другим візиром, а Перт-паша, відповідно — третім. Ці роки пройшли для візира мирно: він досить успішно займався державними справами, не вступаючи в конфлікти з Семиз Алі-пашею.
В 1562 році він одружився з онучкою Сулеймана І і дочки Шехзаде (на той момент) Селіма.
Великий візир
У червні 1565 призначений Сулейманом Пишним великим візиром. В часи правління його сина і наступника Селіма II був фактичним володарем імперії. При ньому турки нарешті оволоділи Кіпром, однак одночасно зазнали поразки в битві при Лепанто.
Всіляко просував по службі своїх родичів. Завдяки його протекції представники роду Соколовичів стали сербськими патріархами.