Сразу после свадьбы она сопровождала царя в паломничестве по монастырям. В июле 1563 года ездила из Александровой слободы с царевичем Иваном Ивановичем на богомолье в Суздаль, а оттуда в Ростов, о чем есть иллюстрация в Лицевом своде.

Скорее всего, в пути молодожены много беседовали, царь жаловался на предателей-бояр. Что могла посоветовать новому мужу Мария Темрюковна, исходя из личного опыта? Только усиливать личную охрану! У черкесов, славящихся горячим нравом, за сабли хватались по любому поводу, и способ выжить у правителя был один – надежная личная охрана. Неважно, из какого ты рода, знатен, или происхождением подл, да пусть хоть иноземец, главное, чтобы полностью зависел от государя и был бесконечно предан. Вот вам и прообраз будущего опричного войска.

Один из самых известных иноземных опричников Генрих Штаден в своих мемуарах прямо указывал, что именно Мария Темрюковна подала Грозному совет о создании опричнины: «Некоторые (из прежних великих князей) заводили было опричные порядки, но из этого ничего не выходило. Также повелось и при нынешнем великом князе, пока не взял он себе в жены княжну, сестру князя Михаила Темрюковича из Черкасской земли. Она-то и подала великому князю совет, чтобы отобрал он для себя из своего народа 500 стрелков и щедро пожаловал их одеждой и деньгами, и чтобы повседневно и днем, и ночью они ездили за ним и охраняли его. С этого и начал великий князь Иван Васильевич всея Руси и отобрал из своего народа, а также и из иноземцев особый избранный отряд. И так устроил опричных и земских».

Эту же версию поддерживает и князь Курбский, отмечавший, что перемена в поведении произошла от влияния «злых жен-чародеиц». И заметим, все это – на фоне военных поражений. Так удачно начавшаяся Ливонская война превратилась для русских в долгую и кровопролитную войну с гораздо более серьезным противником – Речью Посполитой. Поражения проще всего связывать с изменой. Начались репрессии, под которые попали, прежде всего, русские князья и воеводы.