О происхождении Кутуза Макризи сообщает следующее: «Говорят, что его звали Махмуд ибн Мамдуд, что его мать была сестрой султана Джалал ад-Дина хорезмшаха, а отцом его был дядя по отцу султана Джалал ад-Дина. Кутуза взяли в плен татары, которые продали его в Дамаске, откуда он был перевезён в Каир» .
Кутуз, старший эмир му‘иззи, мамлюков аль-Му‘изза Айбека, после прихода к власти последнего занял пост наместника султаната Египта (наиб ас-салтана Миср). В январе 1254 года он принял непосредственное участие в организованном в Каирской цитадели убийстве лидера мамлюков-бахритов эмира Фарис ад-Дина Актая, соперника султана. Многие бахриты, в том числе Бейбарс, опасаясь за свою жизнь, бежали из Каира. Дважды (1257, 1258) они совершали нападения на Египет, но были отражены Кутузом; с пленными бахритскими предводителями он жестоко расправился.
После смерти самого Айбека трон занял его 15-летний сын аль-Мансур Али (март 1257 года), но, фактически, власть делили между собой Кутуз, Санджар аль-Халаби, атабек юного султана, и Санджар аль-Гатми, лидер оставшихся в Египте бахритов. Кутуз смог добиться заключения своего главного противника Санджара аль-Халаби и занял пост главнокомандующего войском (атабег аль-асакир), сосредоточив в своих руках единоличную власть. Узнав о монгольском вторжении в Сирию, Кутуз дождался пока наиболее опасные его противники из фракций салихи и му‘иззи покинут Каир, сместил Аль-Мансура Али и занял престол под титулом аль-Малик аль-Музаффар («всепобеждающий царь») (12 ноября 1259 года). Обоснованием легитимности этой узурпации служило то, что аль-Мансур Али слишком юн, чтобы стать лидером джихада, который надлежит начать против монголов. Возможно, Кутузу было идеологически выгодно заявить о своём происхождении от хорезмшахов, таким образом он мог выступить как мститель за династию, потерпевшую поражение от монголов.
Войска Хулагу взяли Халеб 25 января 1260 года, но айюбид ан-Насир Юсуф, пребывавший в Дамаске, не спешил на помощь городу. Не смог он и договориться с Кутузом о совместных действиях против врага. Бейбарс, находившийся на службе у ан-Насира, покинул его и вместе с большой группой курдов-шахразури отступил в Палестину, где встал лагерем под Газой. Отсюда он начал переговоры с былым врагом Кутузом о получении амана (гарантии безопасности) в случае возвращения в Египет. Хулагу, тем временем, потребовал от Кутуза капитуляции, на что египетский султан ответил казнью монгольских послов.
Египетское посольство отправилось в Акру с целью заключить союз против монголов. Франки решили сохранять нейтралитет, но дали разрешение на проход мамлюкского войска по прибрежной полосе Иерусалимского королевства. 15 июля 1260 г. мамлюки под командованием Кутуза и Бейбарс выступили из Каира и в августе встали лагерем в окрестностях Акры, где отдохнули и пополнили припасы. 3 сентября мамлюки разбили армию Китбуки в битве при Айн-Джалуте. Сирия перешла под контроль мамлюков и Кутуз назначил в города своих наместников. Правителем Дамаска он поставил Санджара аль-Халаби, а обещанный Бейбарсу Халеб отдал Ала ад-Дину Али, сыну мосульского атабека Бадр ад-Дина Лу‘лу‘.
На обратном пути в Египет войска остановились лагерем под Газой. Группа эмиров, среди которых были как бахри (Бейбарс и Балабан ар-Рашиди), так и му‘иззи, составила заговор. 23 октября 1260 года во время охоты Бейбарс приблизился к Кутузу и попросил в дар захваченную в плен монгольскую девушку. Получив согласие, он поцеловал руку султана. По этому условному знаку мамлюки окружили его и убили. Хотя, согласно придворному летописцу Абд аз-Захиру, смертельный удар нанёс Бейбарс, вероятнее всего это сделал малоизвестный мамлюк Анас аль-Силахдар. Новым султаном был выбран Бейбарс.