Что же нам делать? Призвать французов? Невозможна! Покориться им, а тем более призвать их было бы изменой нашему богу, нашей родине и нашей вере.
Французы — воинственная нация, они многочисленны, богаты и жаждут побед. А что мы можем им противопоставить? Племена, враждующие друг с другом; своекорыстных и жадных вождей, стремящихся к личному возвышению; общины, отвергающие всякую власть, одни из которых обогащаются грабежом, другие едва удерживают свое имущество? Силы слишком неравны. При таком положении дел даже представить себе успешную борьбу с неверными было бы глупостью, а начать ее — безумием. Нет, могущественному французскому королю может быть с успехом противопоставлен только такой властелин, который, подобно ему, стоит во главе хорошо организованного государства, располагает богатой казной и послушной армией. Нам нет нужды далеко ходить за таким королем. Султан Марокко уже выражал нам свое сочувствие. Он хорошо знает, что внешняя опасность, которая угрожает нам, может в конце концов обернуться и против него. Его присутствие воодушевит и укрепит нас. Порядок будет установлен. Борясь под его началом, мы добьемся победы, ибо его знамена — знамена бога и пророка».
Махи ад-Дин сумел убедить оранских шейхов в том, что предложенный им выход является единственно разумным в создающейся обстановке.
В середине 1831 года алжирское посольство, сопровождаемое конным отрядом и караваном с подарками, прибыло в столицу Марокко город Фес. Султан Мулай Абдаррахман, соблазненный возможностью расширить свое царство, обласкал оранских шейхов и обещал поддержку. Однако султан не торопился с выполнением своего обещания: он опасался восстановить против себя французское правительство. Только через полгода Абдаррахман решился послать в Алжир войско из пяти тысяч всадников, возглавленных его сыном Мулай Али.
Марокканцы, встречаемые повсюду приветственным ликованием алжирцев, вступили в Оранию и заняли древний алжирский город Тлемсен. Махи ад-Дин, сопровождаемый Абд-аль-Кадиром, отправился в Тлемсен, чтобы заверить марокканского принца в своей преданности. За ним последовали почти все шейхи крупных оранских племен. В Тлемсен стекались многочисленные отряды арабских воинов. Город мог бы стать центром освободительной борьбы против французских захватчиков. Но не стал. Французское правительство предъявило марокканскому султану ультиматум: тот должен либо вывести войска из Алжира, либо вступить в войну с Францией. Султан уступил. По его повелению Мулай Али вернулся в Марокко, оставив в Тлемсене гарнизон во главе с пашой Бен-Нуной.
Алжирцы вновь оказались предоставленными самим себе.
Махи ад-Дин призвал арабские племена к джихаду — «священной войне» против французов. За короткое время он собрал войско в несколько тысяч человек и повел его на штурм Орана. Арабы атаковали Ханк-ан-Натах, крепость на южной окраине города. План штурма составил Абд-аль-Кадир. Он же лично руководил осадой крепости.
Сражение началось атакой арабской конницы, которая загнала в крепость французский отряд, пытавшийся защитить подступы к Орану. После этого алжирцы, спешившись, бросились на штурм. Абд-аль-Кадир, одетый в алый бурнус, появлялся на своем арабском скакуне в самых жарких местах битвы. Сильный орудийный и ружейный огонь со стен крепости заставил алжирцев отступить. Часть осаждавших осталась под стенами в крепостном рву. Плотный огонь неприятеля отрезал их от основных сил арабов. У них кончились боеприпасы. Несколько сот алжирцев оказались совершенно беззащитными под дулами французских пушек. Никто не отважился прийти к ним на помощь. Тогда Абд-аль-Кадир сбросил бурнус, наполнил его ружейными зарядами и сквозь град пуль прорвался на своем скакуне в крепостной ров. Под его руководством воины сумели без потерь отойти от крепости.
В этом бою родилась легенда о неуязвимости Абд-аль-Кадира, которая сопутствовала ему в последующие годы и немало содействовала укреплению его авторитета у суеверного мусульманского воинства. Он и впрямь словно был заговорен от вражеских пуль. При осаде Оранской крепости под ним была убита лошадь, его бурнус был изрешечен пулями. Но и в этом и в многочисленных других сражениях он неизменно выходил невредимым из своих горячих схваток. Лишь однажды, спустя несколько лет, пуля оторвала ему часть уха. Это ранение тщательно скрывал от своих солдат, дабы они не усомнились в его неуязвимости.
Первый бой с французами не принес успеха алжирцам. В нем обнаружились все недостатки племенного ополчения: отсутствие дисциплины и организованности, слабость вооружения, незнание тактики современного боя. Нужно было срочно устранять эти недостатки. Но прежде нужно было найти вождя, который сплотил бы народ и возглавил борьбу против захватчиков.