Первые десять лет мамлюкского правления оказались бурными и переменчивыми. Шаджар Аль-Дурр (1250), бывшая рабыня-наложница и вдова айюбидского султана аль-Салиха, была провозглашена султаной и правила в одиночестве — она была первой и единственной султаной на Среднем Востоке и одной из немногих женщин-правительниц в исламской истории. Ее изображения печатали на монетах, имя произносили в пятничных молитвах, как принято для мужчин-правителей. Но положение ее было непрочным. Сама мысль о независимой женщине-правительнице была противна и Каиру, и Багдаду, где духовный лидер суннитов изрек: «Если среди вас нет ни одного мужчины, достойного стать султаном, я вам такого пришлю. Горе народу, управляемому женщиной». Правление Шаджар длилось всего два месяца, а потом она отреклась от престола и вышла замуж за мягкого нравом полководца Айбека (1250 и 1254–1257) — мамлюка, но не бахри; он сразу же стал султаном. Однако через несколько дней Айбек отказался от власти, и султаном был провозглашен шестилетний кузен Аль-Салиха; всем было ясно, что мальчик — лишь игрушка в руках Айбека, а сам военачальник действует в соответствии с волей Шаджар.

Столь шаткая ситуация таила в себе угрозы — прежде всего, со стороны племен бедуинов (арабов-кочевников) Верхнего Египта, которые дали понять, что никогда не станут подчиняться турецкой рабыне и наложнице, а потому подняли восстание, продлившееся три года. Айюбидские принцы в Сирии считали, что имеют законные права на престол Египта, а потому готовились к войне. Их разбили в восточной части Дельты в 1251 году с помощью бахри, основной военной силы Египта. Но бахри и сами жадно взирали на корону, и Айбек, полагаясь на них, вынужден был постоянно опасаться предательства. Он пригласил к себе лидера бахри под предлогом совещания и казнил возможного соперника, а его голову сбросил со стены Цитадели его братьям по оружию, ожидавшим своего командира. Большинство бахри бежали из страны, и все они готовились призвать к ответу Айбека и его малолетнего султана-марионетку.

Айбек решил, что пора ограничить влияние Шаджар, и задумал взять еще одну жену — принцессу Мосула. В приступе ревности султанша организовала убийство мужа, но когда был нанесен роковой удар, поняла, что совершила трагическую ошибку, и его смерть будет означать и ее собственную гибель. Как гласит история, Шаджар заперлась в башне Цитадели и перетерла в пыль драгоценные камни, чтобы ни одна женщина не смогла носить ее украшения. Когда она вышла наружу, разъяренные наложницы Айбека забили ее до смерти деревянными скалками, а потом бросили тело на съедение бродячим собакам. Останки Шаджар подобрали и захоронили в пышной гробнице, которую она выстроила заранее; ее эпитафия гласит: «О, ты, стоящий над моей могилой, не удивляйся моему положению. Вчера я была такой, как ты, а завтра ты станешь таким, как я».

Сын Айбека, подросток Али (1257–1259), стал султаном, но фактически лишь изображал правителя, а реальная власть оказалась в руках военачальников мамлюков. Кутуз (1259–1260), который убил лидера бахри по приказу Айбека несколькими годами ранее, мало-помалу уничтожил всех соперников и узурпировал трон. Нет сомнения, ему помогло общее убеждение в необходимости сильного правителя — ведь обозначилась явная угроза: колоссальная армия монголов численностью 120 000 человек приближалась к Египту.

В 1258 году монголы, возглавляемые ханом Хулагу, внуком Чингисхана, разграбили Багдад, превратили этот прекрасный город в руины, перебили большинство обитателей, включая халифа династии Аббасидов, духовного лидера мусульман-суннитов. Лишь зловоние от трупов, гнивших на улицах, положило конец зверствам, заставив захватчиков отойти от города. К 1260 году монголы пересекли Евфрат и начали продвижение по северной Сирии, сравняли с землей крепость Алеппо, а потом свернули на юг, чтобы взять Дамаск и уничтожить еще одно автономное владение Айюбидов. Следующим был Египет.

Монголы направили в Каир послов с требованием к «выскочкам-рабам из мамлюков» сдаться. Кутуз казнил послов. Этот поступок обеспечил ему поддержку бахри, которых возглавлял харизматический лидер Бейбарс (1260–1277), решивший, что лучше объединиться со старым врагом, чем позволить монголам уничтожить Каир.

К счастью для мамлюков, смерть великого хана монголов в Центральной Азии отвлекла значительные силы во главе со свирепым Хулагу, который погряз в борьбе за власть в Орде. Остатки монгольской армии были разбиты Кутузом и Бейбарсом при Айн-Джалуте, неподалеку от Назарета (1260). Лишь немногие монголы смогли выбраться живыми с поля боя и спрятаться в тростниковых зарослях по берегам реки Иордан, но египтяне подожгли тростник. Это была решающая победа, которая сдержала продвижение монголов, позволила мамлюкам занять значительную часть Сирии и сокрушила миф о непобедимости монголов. Дважды мамлюки спасли Египет и ислам от неверных (сперва — от крестоносцев, теперь — от монголов), и благодарное население об этом не забыло.

Кутуз проявил в битве замечательные качества лидера, но потом таланты правителя его словно бы оставили. Перед сражением он дал военачальникам множество обещаний, но после победы будто забыл о них. Бейбарс, которому он обещал пост наместника Алеппо, не скрывал недовольства; когда Кутуз возвращался в Египет, группа недовольных, включая Бейбарса, устроила засаду и убила султана. Новым правителем Египта стал Бейбарс.

Эпоха мамлюков началась с правления Бейбарса (1260–1277). Отвергнутый первым хозяином из-за катаракты на одном глазу, Бейбарс тем не менее пробился в царскую армию султана Аль-Салиха (1240–1249) и быстро пошел в гору. Физический дефект отлично восполнялся крепким телосложением и неистощимой энергией, которая завоевала ему доверие и симпатии подчиненных. Став султаном Египта, он выказал себя хитроумным политиком, сократив налоги — что принесло ему популярность в народе — и одновременно умаслив богатых предоставлением мест при дворе; при этом на ключевые посты он, разумеется, поставил верных ему мамлюков.

Главной проблемой для бывшего раба, занявшего место султана, было обеспечение легитимности правления. Поскольку утверждения Бейбарса, что он унаследовал царские качества от бывшего повелителя и хозяина Аль-Салиха благодаря обучению и верной службе, звучали не слишком убедительно, были придуманы другие объяснения. В частности, при дворе внезапно появился человек, якобы приходившийся дядей последнему халифу династии Аббасидов, и его с большой помпой провозгласили новым халифом. В ответ новый халиф официально объявил Бейбарса султаном, а Каир — его столицей, сделав город духовным центром суннитов, что придало респектабельности и законности мамлюкскому султанату. Однако халиф оказался слишком амбициозным и гораздо менее покладистым, чем рассчитывал Бейбарс, так что его послали с небольшим отрядом на самоубийственную миссию по освобождению Багдада, из которой он, естественно, не вернулся. Этого халифа сменил другой, поселившийся во дворце за пределами Каира, где он находился фактически под домашним арестом: его вывозили только на официальные государственные и религиозные церемонии.