Во времена халифата в западной части Сахары жило племя из берберского клана санхаджи, которое называло себя лемтуна. Это были простые кочевники, никогда не возделывавшие землю и не знавшие хлеба: они питались только мясом и молоком, которые давал им скот. Люди лемтуна отличались от других берберов тем, что носили покрывала, закрывавшие всю нижнюю половину лица. Покрывало это называлось лисам, а носившие его члены племени – аль-мулассимун («носящие лисам»). Всех, кто ходил с открытыми лицами, лемтуна презирали.
В IX веке аль-мулассимун обратились в ислам, а в XI-м объединились под началом одного вождя – эмира Абу Абдаллаха. Спустя какое-то время его преемник Яхья ибн Ибрахим, возвращаясь из паломничества в Мекку, попросил одного из законоведов в Кайруане прислать своего ученика, чтобы тот научил его племя Корану и сунне. Но ехать в пустыню к грубым и диким кочевникам никому не хотелось, и лишь один человек из Марокко согласился отправиться с опасной миссией на край света: это был проповедник Абдаллах ибн Ясин.
Как выяснилось позже, Ибн Ясин был большим любителем женщин и довольно сомнительным законоведом, но при этом обладал личным обаянием и миссионерской жилкой. Его появление в Сахаре полностью перевернуло жизнь летумна. Можно сказать, что именно проповедь Ибн Ясина создала Альморавидскую династию.
Начало миссии оказалось не совсем удачным: суровые требования к дисциплине и самоограничению, накладываемые самым строгим, маликитским толком шариата, приверженцем которого был Ибн Ясин, оттолкнули большинство кочевников. Ему пришлось удалиться в отдаленный рибат (крепость) на реке Сенегал, где он и его немногие последователи организовали общину «людей рибата» – аль-мурабитун, или искаженно – альморавидов. Члены этого монашеского братства соблюдали постоянный пост, пили только молоко, проводили время в молитвах и готовились к войнам за ислам. Вступавшие в ряды альморавидов отказывались от своего прошлого и получали наказание соответственно своим прежним грехам: за пьянство – 80 ударов плетью, за разврат – 100. Любой проступок в рибате также наказывался кнутом: 5 ударов за опоздание на молитву, 20 – за сокращение числа поклонов и т. д.
Со временем слухи о святых воинах из крепости стали распространяться среди берберов и привлекать к ним новых членов. Во главе этой армии ревнителей веры встал один из вождей племени лемтуна Яхья ибн Омар. Довольно быстро он сумел захватить город-государство Сиджильмасу, где после Мидраридов правил один из вассалов кордовских Омейядов. После этой победы ревностный Ибн Ясин приказал уничтожить в городе все увеселительные заведения и музыкальные инструменты.
Позже, когда Яхья умер, армию возглавил его брат Абу Бакр, не менее талантливый и воинственный руководитель. Продолжая завоевания брата, он с боями взял марокканский город Агмат и женился на вдове местного царя по имени Зейнаб.
Но после первых успехов для Альморавидов настали трудные времена. Ибн Ясин погиб в войне с еретиками из племени бергвата (1059). С востока стране угрожало государство Хаммадидов, захвативших Фес, а на юге Абу Бакру пришлось усмирять берберов в пустыне. В Магрибе вместо него остался править его двоюродный брат Юсеф ибн Ташфин, к которому вместе с властью Абу Бакра перешла и его жена Зейнаб.
Об этой необычной женщине стоит сказать отдельно. В суровом мире воинов и аскетов она занимала высокое положение, мало характерное для стран ислама. Ходила легенда, что Зейнаб была сказочно богата и после замужества обогатила Абу Бакра, приведя его с завязанными глазами в пещеру, полную золота и самоцветов. Ей приписывали способность общаться с джиннами и околдовывать чарами людей: так объясняли умение Зейнаб вести переговоры и ее странную власть над обоими мужьями. Говорили, что не Абу Бакр и не Ибн Ташфин, а она на самом деле правит государством. Помимо всего прочего, Зейнаб была необыкновенно красива и умна – в этом с ней не мог соперничать никто из женщин, живших в то время.
Личность и влиятельность Зейнаб произвели на берберов такое впечатление, что после ее смерти знатные женщины Альморавидов получили особые права, каких не было ни в одной другой династии Магриба. Они не носили паранджу, получали полноценное образование и участвовали в государственных делах. В альморавидской империи было известно немало талантливых поэтесс и по меньшей мере две женщины-врача.
Считается, что именно ибн Ташфин – с помощью Зейнаб или без нее – создал величие Альморавидов. Как писал современник, это был «смуглый, среднего роста человек, худощавый, с небольшой бородой, с приятным голосом, черными глазами, орлиным носом, прядью волос, спадающих на ухо, насупленными бровями, вьющимися волосами. Он был храбр, решителен, величественен, деятелен, великодушен, добр; он презирал светские удовольствия; суровый, справедливый и святой, он был очень скромен и носил только шерстяную одежду; он питался ячменем, мясом, верблюжьим молоком и строго придерживался этой пищи до самой смерти».
Благочестие Ибн Тафшина завоевало ему симпатии многих мусульман, а смерть Абу Бакра в очередном походе сделала его полновластным правителем Западного Магриба (1088). Встав во главе армии, он быстро расширил территорию государства и завоевал значительную часть Среднего Магриба, захватив города Фес и Танжер и осадив Алжир. Во время этих походов Ибн Тафшин основал новый военный лагерь, который со временем превратился в город Марракеш.