For much of the 1150s, however, Abd al-Mu'min concentrated his efforts on expanding eastwards in North Africa. 1151, he had reached Constantine where he confronted a coalition of Arab tribes that had been marching through Berber lands. Rather than the destruction of these tribes, he utilized them for his campaigns in al-Andalus and they also helped to quell any internal opposition from the family of Ibn Tumart. Abd al-Mu'min led his forces to conquer Tunis in 1159, going on to progressively establish control over Ifriqiya by conquering the cities of Mahdia (then held by Roger II of Sicily), Kairouan, and other coastal cities as far as Tripoli (in modern-day Libya). He then returned to Marrakesh and left for an expedition to Al-Andalus in 1161. Abd al-Mu'min had ordered the construction of a new citadel at Gibraltar, where he based himself during his stay in Al-Andalus.