Преемник Селима Сулейман Великолепный (или Кануни), правивший с 1520 г. по 1566 г., был женат первоначально на черкешенке, «una donna circassa» (по итальянским источникам). «Можно предположить, — пишет E. Н. Кушева, — что она была из бесленейского княжеского рода Кануковых: в первой половине XVI в. при турецком дворе служил один из Машуковых, очевидно, сын Машука Канукова, вступившего в 1550–е годы в сношения с Москвою». Сын этой черкешенки Мустафа считался наследником престола, но затем был заподозрен в измене и казнен вместе со своим малолетним сыном по приказу Сулеймана. По мнению К. Ф. Дзамихова, это произошло около 1552 года и стало причиной отъезда из Константинополя «в Москву к Ивану Грозному князя Ага — Маашукова Черкасского». Возможно, что первые посольства черкесских князей в Москву были, во многом, следствием гонений на черкесскую партию в Стамбуле. Впрочем, гнев султана был обращен против какой‑то одной группировки черкесской знати. В большой чести у султана был прославленный черкесский военачальник Оздемир — паша. П. М. Хольт указывает на то, что он был родственником Кансав Гура. На основании отрывочных сведений можно предположить, что Оздемир был сыном двоюродного брата Кансав Гура, эмира Бибарса, погибшего в несчастной битве на Дабикском поле. С 1549 года Оздемир — паша был наместником (бейлербеем) Йемена. До этого он являлся командующим османскими отрядами в этой стране. «По данным османских источников, — пишет Н. А. Иванов, — Оздемир — паша взял семь крупных крепостей (Хаулан, Атра, Ханфар, Хабаш, Сакейн и др.), являвшихся главными базами шиитского сопротивления, и умиротворил страну». В благодарность за столь блестящие победы Сулейман назначил его наместником Йемена. Оздемир — паша, управляя этой страной, убедился в необходимости контроля над противоположным берегом Красного моря и проливом Баб эль — Мандеб, что положило бы конец пиратским рейдам португальских эскадр. Он составил план завоевания Судана и Эфиопии и представил его на рассмотрение султану. В 1555 году Сулейман Великолепный одобрил предложения полководца и назначил его пожизненно наместником всех земель, которые тот намеревался завоевать.
Оздемир — паша навербовал экспедиционный корпус в Египте: помимо мамлюкской кавалерии в него вошла боснийская пехота. По мере продвижения вверх по Нилу Оздемир оставлял гарнизоны в захваченных городах и назначал там мамлюкских наместников. Он занял Массауа в 1557 году, и тогда же выбил португальцев из Зайла, порта на южном берегу Аденского залива. «Создатель эйалета Хабеш и красноморского просперити, — заключает Н. А. Иванов, — Оздемир — паша умер в Дыбароа в 1559 году. Через десять лет его прах был перенесен в Массауа. Здесь его сын Осман — паша, бей-лербей Йемена в 1568–1569 гг., построил великолепную мечеть с усыпальницей, где были захоронены останки великого гази, защитившего ислам от угрозы португальского завоевания».