
Cu toate acestea, pentru cea mai mare parte a anilor 1150, Abd al-Mu'min și-a concentrat eforturile pe extinderea spre est în Africa de Nord. În 1151, ajunsese la Constantin, unde s-a confruntat cu o coaliție de triburi arabe care mărșăluiseră prin ținuturile berbere. Mai degrabă decât distrugerea acestor triburi, le-a folosit pentru campaniile sale din al-Andalus și, de asemenea, au ajutat la înăbușirea oricărei opoziții interne din partea familiei lui Ibn Tumart. Abd al-Mu'min și-a condus forțele să cucerească Tunisul în 1159, continuând să stabilească progresiv controlul asupra Ifriqiya prin cucerirea orașelor Mahdia (pe atunci deținute de Roger al II-lea al Siciliei), Kairouan și alte orașe de coastă până la Tripoli ( în Libia actuală). Apoi s-a întors la Marrakech și a plecat într-o expediție în Al-Andalus în 1161. Abd al-Mu'min ordonase construirea unei noi cetăți la Gibraltar, unde s-a stabilit în timpul șederii sale în Al-Andalus.