Гибель талантливого полководца Мюрида заставила поднять голову многих его конкурентов в борьбе за трон. Азиз-Шейх, еще один потомок Шибана, приходившийся Мюриду двоюродным племянником, провозгласил себя ханом и начал чеканить монету в Гюлистане. Ему противостоял его дальний родич — вышеупомянутый Мир-Пулад, изгнанный Мамаем из Сарая, но все еще не покинувший Поволжья. Однако против Мир-Пулада выступил очередной претендент — Пулад (Деулиуллах)-ходжа, потомок Туга-Тимура, заставивший Мир-Пулада окончательно распроститься с претензиями на сарайский трон и вернуться в свои владения в Приаралье.[162]

Пулад (Деулиуллах)-ходжа сумел опередить Азиз-Шейха и первым занять столицу. Едва ли не первым его актом стала отмена ярлыка Абдаллаха на великое княжение Дмитрию Московскому и выдача нового ярлыка Дмитрию Суздальскому. Однако к этому времени суздальский князь в значительной степени утратил свои амбиции и отказался от претензий на великий стол, а вскоре и породнился со своим московским соперником, выдав замуж за него свою дочь Евдокию. А вскоре Пулад (Деулиуллах)-ходжа был убит собственными эмирами — согласно Муин ад-Дину Натанзи, за чрезмерно жестокое правление.[163]

Азиз-Шейх, избавившийся, таким образом, от двух соперников, практически беспрепятственно занял столицу и активно занялся укреплением власти над русскими княжествами. Он отправил на Русь своего посла Байрам-Ходжу, через которого потребовал у русских князей вновь признать власть Сарая и платить ему дань. В 1365 г. Азиз-Шейх выдал ярлык на Нижний Новгород князю Борису Константиновичу Городецкому, спорившему за этот город (оставшийся выморочным после смерти его старшего брата Андрея) со своим братом Дмитрием Суздальским.[164] Кроме того, в 1367 г. хану удалось покончить и с независимостью Волжской Булгарии: местный правитель Пулад-Тимур совершил неудачный поход на Русь, был разгромлен русскими на Пьяне, и Азиз-Шейх, воспользовавшись его неудачей, обрушился на мятежного эмира, захватил его в плен и казнил.[165] Наместником Волжской Булгарии стал лояльный сарайским ханам эмир Асан. Казалось, новый властитель Золотой Орды имеет все шансы восстановить былое могущество сарайского престола.

Что же делали в это время Мамай и Абдаллах? Прежде всего, им пришлось навести порядок в собственных владениях в Крыму, где местные правители, прежде поддержавшие Мамая, после сарайской неудачи вышли из-под его контроля. Так, солхатский даруга Кутлуг-Буга отказался повиноваться Мамаю и даже начал возводить вокруг Солхата оборонительный ров, надеясь, что он защитит его в случае нападения бекляри-бека.[166] Узнав об этом, Мамай со всеми силами поспешил к городу, прежде находившемуся под властью его предков, и осадил его. Армянский современник, переживший осаду Солхата, записал 23 августа 1365 г., что «люди и животные со всей страны, простиравшейся от Кец (Керчи) до Сарукармана (Херсонес), собрались тут; и Мамай [сейчас] в Карасу с многочисленными татарами; и наш город дрожит и шатается …»[167] Оборонительный ров не пригодился: жители Солхата предпочли не искушать судьбу и сдали город Мамаю, который даже позволил Кутлуг-Буге остаться и сохранить пост даруги.[168]

Стоит отметить, впрочем, что Мамай, фактически сделав Солхат своей штаб-квартирой, не превратил его в военный лагерь: город продолжал оставаться одним из важнейших торговых и культурных центров Крыма. За время нахождения здесь ставки Мамая активно развивались также научная и литературная деятельность и даже книжная торговля.[169]

Уладив дела на полуострове, Мамай и Абдаллах начали враждебные действия против сарайского хана Азиз-Шейха. Прежде всего Абдаллах с подачи Мамая выдал ярлык на Нижний Новгород Дмитрию Константиновичу Суздальскому — в противовес ярлыку, выданному Азиз-Шейхом Борису Константиновичу, брату Дмитрия. Таким образом Мамай и «его» хан демонстрировали, с одной стороны, противостояние сарайскому монарху, с другой — поддержку своему вассалу и союзнику Дмитрию Московскому, который к этому времени помирился и даже породнился с Дмитрием Суздальским.

Однако подобные действия были лишь незначительным внешним проявлением враждебности Мамая и Абдаллаха по отношению к Азиз-Шейху. Гораздо более важную работу Мамай вел скрытно: в течение 1365-1367 гг. его сторонникам в Сарае удалось переманить на сторону Мамая и Абдаллах-хана нескольких эмиров Азиз-Шейха (возможно, подкупив их при помощи русского серебра), которые составили против него заговор. В результате в 1367 г. сарайский хан был зарезан своими приближенными прямо в собственной постели. Впоследствии заговорщики стали распространять слухи, что Азиз-Шейх поплатился жизнью якобы за установление им «скверных обычаев», за которые его порицал влиятельный представитель мусульманского духовенства Сайид-Ата и которые хан пообещал отменить, но не сдержал обещания.[170] Однако после его смерти Сарай беспрепятственно был занят Абдаллахом и Мамаем, и это дает веские основания полагать, что покойный хан пал жертвой заговора, организованного бекляри-беком.