Рустем назначается бейлербеем Анатолии. В 1539 г. одновременно с торжествами по поводу обрезания шахзаде Баязида и Джахангира состоялись свадебные торжества по случаю свадьбы дочери султана Сулеймана Михримах-султан. При этом Рустем-паша получает звание третьего визира, а в 1541 г. – второго. Стараниями Хуррем в 1544 г. султан Сулейман назначает Рустем-пашу великим визиром.

После этого замужества создается группировка в составе Хуррем-султан, ее дочери Михримах-султан и Рустем-паши. Основной их целью было устранение Мустафы с пути детей Хуррем-султан к трону. Несмотря на все попытки Хуррем-султан и Михримах-султан, ее муж Рустем-паша не сумел занять место Ибрагим-паши, что давало бы ему право войти в султанские покои.

Тем не менее, по свидетельствам современников, он стал главным исполнителем задумки Хуррем-султан устраннить Мустафу. Хуррем-султан была вдохновительницей иранского похода, который начался в 1548 г. Она надеялась, что во время этой экспедиции ее зять Рустем-паша и ее сыновья покажут себя с выгодной стороны. Во время этого похода ее сын Селим был назначен на должность каймакам, который должен был охранять западные границы империи от внезапного нападения на Османскую империи с запада. А другой сын, Баязид, со своими вооруженными силами присоединился отцу, когда тот находился в Халебе. При этом старший сын Мустафа оставался в своем санджаке не у дел, несмотря на то, что поход совершался на государство Сефевидов. А его санджак Амасья находился непосредственно близ территории, где происходили военные события. Видимо, Мустафа нервничал и чувствовал изменившееся отношение своего отца к себе.

По словам турецкого историка Т. Гекбилгина, Рустем-паша от имени шахзаде Мустафы сочиняет ложные письма шаху Ирана Тахмаспу и запечатывает их печатью Мустафы. Он также задерживает курьера с письмами от иранского шаха и доносит о них султану Сулейману92. В результате ложного донесения Рустем-паши о том, что якобы шахзаде Мустафа готовит восстание янычар, чтобы отстранить султана от власти, Сулейман в 1553 г. приказывает казнить своего старшего сына93. Обозленные этим происшествием янычары разграбили шатер Рустем-паши и вынуждают султана снять его с должности великого визира. В одном из своих писем Хуррем-султан просит султана Сулеймана не казнить Рустем-пашу. В результате интриг хасеки Хуррем-султан и дочери Михримах-султан в 1555 г. Сулейман приказывает казнить великого визира Кара Ахмед-пашу и на его место назначает Рустем-пашу, который остается на этой должности до своей смерти в 1561 г.94

В 1542 г. Хуррем удалось нарушить еще одну традицию, которая сложилась с середины XV в., согласно которой матери шахзаде сопровождали своих сыновей при управлении ими санджаками. При отправке Мехмеда, любимого сына Сулеймана и Хуррем, в санджак Маниса она осталась в столице и не поехала вместе с сыном, как поступали ее предшественницы. До сих пор ведутся научные споры о причинах такого поступка. Среди них упоминается то, что последний сын Хуррем, Джахангир, был горбатый и постоянно болел. Необходимо было, чтобы мать оставалась при нем. Однако болезнь Джахангира не помешала Хуррем посещать своих сыновей в санджаках. В 1543 г. Хуррем посетила своих сыновей Мехмеда в Манисе и Селима в Коньи, где они правили этими санджаками. Другие исследователи указывают, что положение Хуррем заставляло ее не соблюдать это правило, поскольку каждый из ее сыновей, с которым она отправлялась в санджак, получал бы определенное преимущество в борьбе за престол95.

Несмотря на свой грозный вид и жестокость по отношению к врагам, по природе своей Сулейман, возможно, очень часто попадал под влияние какого-либо доверенного лица. В годы его правления на Сулеймана оказывали сильное влияние его мать Хафза-султан, Ибрагим-паша, Хуррем-султан, его дочь Михримах-султан и внучка Хумашах-султан, дочь его любимого сына шахзаде Мехмеда, который умер в 1543 г. С другой стороны, Сулейман доверял некоторым своим приближенным, среди которых были Рустем-паша, Соколлу Мехмед-паша и Эбуссууд-эфенди. Одновременно с выдвижением на первый план своих фаворитов сам султан стал менее доступен подданным. Он все больше ограничивал доступ к себе другим высокопоставленным должностным лицам, что еще больше усиливало власть фаворитов.

Некоторые исследователи предполагают, что хасеки султана Селима II Нурбану-султан по происхождению была из знатной венецианской семьи96. Ее отец Николо Веньер был назначен на правление островом Парос, где от дочери другой венецианской аристократической семьи, Виоланте Баффо, в 1525 г. родилась его дочь Сесилия Веньер-Баффо. Николо Веньер к этому времени был женат на другой женщине, от которой имел сына. Возможно, по этой причине он официально не мог жениться на Виоланте Баффо. В 1537 г., когда ей было двенадцать лет, в пути на остров Корфу Сесилия Веньер-Баффо была захвачена моряками османского адмирала Барбароса Хайреддин-паши. По возвращении в столицу Османской империи в качестве подарка она была преподнесена Хуррем-султан и попала в султанский гарем, где получила имя Нурбану. У нас нет достоверных сведений о жизни Нурбану в султанском гареме. Как и все остальные девушки в гареме, она обучалась и воспитывалась под наблюдением опытных наставниц. Возможно, там шахзаде Селима Нурбану оказалась в 1543 г., когда тот управлял санджаком Конья. После неожиданной смерти шахзаде Мехмеда в 1543 г. Селим был назначен правителем санджака Маниса, где в 1544 г. у Нурбану родилась первая дочь Шах-султан. После нее друг за другом родились ее дочери Джев-херхан-султан (1544) и Исмихан-султан (1545)97. В 1546 г. родился шахзаде Мурад. Во время правления в различных санджаках у Селима были множество наложниц. Венецианский посол Доменико Тревизано в своем отчете Сенату указывал, что Селим был тучного телосложения и имел пристрастие к вину и женщинам98. Тем не менее Нурбану была матерью всех его детей, родившихся до его вступления на престол99. Возможно, предпринимались определенные меры, чтобы не рождались дети от других его наложниц100.

Пользуясь благосклонностью шахзаде Селима, она стала играть важную роль в его гареме. Зная о его любвеобильности, она не устраивала сцены ревности, как это делала Хуррем-султан. С помощью своих людей в гареме она контролировала действия других наложниц. Вероятно, одна из причин отсутствия детей Селима от других его наложниц кроется в том числе и в действиях Нурбану. Одним из примеров может послужить ее отношение к наложнице по имени Гюльпери, которая была подарена Селиму его сестрой Михримах-султан в знак примирения после устранения основного претендента на престол шахзаде Баязида, который в это время вынужден был убежать к иранскому шаху Техмаспу. Чтобы очернить Гюльпери в глазах Селима, люди Нурбану подкладывают кинжал в ее вещи. В гареме распускают слух о том, что Гюльпери специально послана Рустем-пашой и Михримах-султан, чтобы убить Селима. В таком случае у шахзаде Баязида появляются определенные шансы, чтобы стать султаном в случае смерти Сулеймана. Эти слухи, доведенные до шахзаде Селима соответствующим образом, вынуждают его удалить из своего гарема эту красивую наложницу, что усилило влияние Нурбану, которая раскрыла этот «заговор»101. Возможно, она не первый раз использовала такие уловки.