Construction was also aided by additional funds donated by a group of local residents of Andalusi background, which gave the mosque its current name.

According to the 12th-century Andalusian geographer Al-Bakri, the mosque consisted of a hypostyle hall with six aisles (or seven, according to al-Jazna'i) formed by parallel rows of horseshoes arches supported on stone columns.

[3] The construction of both minarets was carried out by the local Zenata governor, Ahmed ibn Abi Said, a vassal of the Umayyads,[7] but it is unclear exactly what personal involvement Abd ar-Rahman III had in the project beyond providing the funds.

In 985 Ibn 'Abi Amir, the vizier of Caliph Hisham II and de facto ruler of Cordoba (known in Christian sources as Almanzor), sent his cousin Askalaja with an army to retake Fez and northern Morocco directly.

Terrasse suggests that the earlier inscription of 369 AH (which does not include any names) was left in place at the time because the local craftsmen, who may not have been able to read Kufic well, might not have realized its significance.

[5]: 11  Terrasse remarked that this long period, as well as the relatively homogenous fabric of the current building (which has brick pillars instead of stone columns), suggests that the mosque was almost entirely reconstructed at this time.

Most of the minbar, especially its sides, were covered with new wooden panels decorated in the Moorish style of this period, strongly influenced by Andalusi craftsmanship.

The upper back panel, however, which featured inscriptions from the 10th-century Umayyad restoration, was preserved in place, perhaps indicating a certain respect the Almohads held for the former Caliphate of Cordoba.

[5]: 39–40 Terrasse remarks that the masonry used in the Almohad construction was of mediocre quality, requiring that it be repaired and restored in the late 13th century under the Marinids.

[5]: 11–12  Although not mentioned in historical sources, Terrasse believed that the eastern gate of the mosque, near the minaret, was likely built or decorated in the 14th century, perhaps also under Abu Thabit.

[5]: 12  The Dar al-Muwaqqit, an apartment for the timekeeper built on the second floor, on the southeast side of the minaret, probably also dates from the Marinid period, when such structures began to be added to mosques.

A large storage space at the back of the mosque, with a cursive inscription panel above its double doors, appears to have served as a library and was founded by one of the last Marinid sultans, Abu Sa'id Uthman III, in 1415 (816 AH).