Соколлу Мехмед-паша управлял империей Селима II, фактически являясь олицетворением власти османской династии, тогда как сам султан оставался в стороне от связанного с ожесточенными спорами процесса принятия решений. Этот незаурядный человек в течение четырнадцати лет, при трех султанах, бессменно находился на посту великого визиря. Он родился в семье не обладавшего большим влиянием сербского аристократа Соколовича («Сын сокольничего») и был типичным продуктом проводившегося в империи набора юношей. Во времена правления Сулеймана он легко поднимался по иерархической лестнице. Его первым значительным постом стала должность адмирала флота, которую он получил после кончины Барбароссы. Затем он был губернатором нескольких важных провинций и командующим войсками на западных и восточных рубежах империи, пока в 1565 году Сулейман не назначил его великим визирем. Опасные последствия, вызванные попыткой Сулеймана предотвратить столкновение своих сыновей, позволили Соколлу Мехмед-паше продемонстрировать династии свою ценность. В 1555 году ему было доверено подавление мятежа поднятого самозванцем, «Лже»-Мустафой, а в 1559 году, являясь командующим армией, направленной Сулейманом на помощь Селиму, сражавшемуся со своим братом Баязидом, он доказал будущему султану свою незаменимость. Своей победой Селим был обязан Соколлу Мехмеду, и если принц не скупился на вознаграждения, то Сулейман еще прочнее связал Соколлу Мехмеда с династией, женив его в 1562 году на дочери Селима, Эсмахан Султан (чтобы ничто не мешало ему принять столь высокое предложение, Соколлу Мехмед развелся с двумя другими женами). Отношения этого талантливого политика и военачальника со своим владыкой чем-то напоминали отношения Ибрагима-паши с Сулейманом. Подобно тому, как это было с Ибрагимом, особый статус Соколлу Мехмеда подтверждался местоположением его дворца, находившегося на Ипподроме, неподалеку от дворца его владыки.
В первые годы правления Селима турки были заняты проведением небольших, но весьма важных операций на своих дальних рубежах. Когда в 1567 году известие о кончине Сулеймана достигло провинции Йемен, могущественный глава рода Зайди, имам Мутаххар ибн Шараф аль-Дин, объединил своих последователей-шиитов и поднял мятеж. Османская власть в Йемене всегда была достаточно слабой. Оказалось, что на этой труднопроходимой и редко населенной территории невозможно подчинить независимых вождей местных арабских племен, а общего с турками исламского вероисповедания было недостаточно для того, чтобы гарантировать их согласие с введением совершенно чуждого им режима. Для подавления недовольных новой властью требовалось строительство крепостей и размещение в них гарнизонов, поэтому контроль над этой провинцией обходился весьма дорого, и хотя за время своего, продолжавшегося с 1549 по 1554 год, губернаторства энергичный Оздемир-паша сделал османское правление в ней более эффективным, его преемники на этом посту оказались более слабыми правителями. В 1565 году Йемен был разделен на две провинции, но османский губернатор южной провинции с центром в Сане был убит, а многие опорные пункты, которыми прежде владели турки, теперь перешли к имаму Мутаххару.
Йемен был важен потому, что он давал возможность контролировать маршрут, по которому перевозили пряности, а таможенные сборы за провоз этого товара приносили доходы в казну Османской империи. В 1568 году на усмирение этой провинции были направлены значительные экспедиционные силы под командованием бывшего наставника султана Селима и его доверенного лица, Лала Мустафа-паши. Такой выбор говорил о том, что Селим все же не был целиком во власти своего великого визиря, поскольку вхождение Лала Мустафы-паши в число тех, к кому султан испытывал привязанность, вызывало у Соколлу Мехмеда негодование. Для того чтобы подавить мятеж в Йемене, Лала Мустафе были нужны людские ресурсы и снабжение из Египта, но губернатор этой провинции и еще один его соперник, Коджа («Великий») Синан-паша, отклонил его просьбы и сделал невозможным выполнение целей, поставленных перед экспедицией. В потоках донесений, отправленных в Стамбул, каждый из этих двоих отстаивал свою позицию. Коджа Синан оказался убедительнее и Лала Мустафа был отстранен от командования войсками в Йемене. Но чтобы показать, что он по-прежнему проявляет к нему благосклонность, Селим ввел специально для него должность шестого визиря в правящем совете империи. Руководство ведением военной кампании перешло к Кодже Синану, но трудности со снабжением войск, сражавшихся в Йемене, заставили его прийти к соглашению с родом Зайди. Две йеменские провинции были снова объединены, и к 1571 году Коджа Синан уже мог возвращаться в Каир. Нестабильность в этом регионе привела к тому, что турки снова стали рассматривать возможность строительства канала, соединяющего Средиземное и Красное моря. Вот что имперский указ предписывал осуществить губернатору Египта: