In Yamen, Ali Muhammad al-Sulayhi had established the Sulayhid rule and introduced the Fatimid khutba. In 450/1058, he succeeded to expel the Zaidis from San'a, and made it his capital. In 452/1060, he captured Zabid after killing Sa'd bin Najah, the founder of the Najahid dynasty and appointed his brother-in-law, Asad bin Shihab as the governor of Zabid. In 454/1062, he conquered Adan, where he allowed Banu Ma'n to rule for sometime as tributaries of the Sulayhids. Later, in 476/1083, the Sulayhids granted the governorship of Adan to two Hamdani brothers, Abbas and Masud bin Karam, who founded the Ismaili dynasty of the Zurayids in Adnan from 476/1083 to 569/1173. In sum, Ali bin Muhammad subjugated all of Yamen in 455/1063 and also extended his influence from Mecca to Hazarmaut. Umara bin Ali al- Hakami (d. 569/1174) writes in 'Tarikh-i Yamen' (tr. Henry C. Kay, London, 1892, pp. 24-5) that, 'None of its plains or its hills, of its lands or of its waters remained unsubdued. No parallel case can be found of so rapid a conquest, either in the days of ignorance or in the days of Islam.' One of the greatest achievements of Ali bin Muhammad al-Sulayhi was his success in establishing peace in Mecca on behalf of al-Mustansir.
In 454/1062, Ali bin Muhammad al-Sulayhi desired to meet al-Mustansir, therefore, he sent Lamak bin Malik al-Hammadi, the chief qadi of Yamen to Cairo to discuss his prospective visit. In 454/1062, Nasir ad-Dawla had begun to ravage Egypt, therefore, qadi Lamak had to stay with al-Muayyad at the Dar al-Hikmah. Lamak remained in Cairo for five years and at length he had an audience with al-Mustansir. On the other hand, Ali bin Muhammad set out on a pilgrimage to Mecca in 459/1067 at the head of 2000 horsemen of whom 160 were the members of his household. Unfortunately, he was killed with a number of his relatives in a surprise attack by the sons of Sa'd bin Najah in reprisal of his father's death. His son Ahmad al-Mukarram was declared the head of Yamen by al-Mustansir. The rule which Ali bin Muhammad al-Sulayhi founded would have fallen to the ground if his son Ahmad al-Mukarram had not come to its rescue and restored it.
In one of the rare extant letters from Yamen to al-Mustansir, Ahmad al-Mukarram, after giving an account of the death of his father and the following events, reports that the envoys of the dai of India have brought him a letter, asking that permission be granted to them to pass from verbal propaganda to the use of force. It shows that there were preparations for a rising on the western coast of India, presumably in Gujrat, ruled by the then Hindu Chaulukya dynasty and establish there a Fatimid enclave. In his letter dated 461/1068, the Imam replied to the question of the dai Yousuf bin Hussain and left it to him to judge whether the plan was feasible. Nothing seems to have come of it. In 468/1075, Yousuf bin Hussain died in India, therefore, Ahmad al- Mukarram was commissioned to choose his successor. Yousuf's son Ahmad was proposed by him, which the Imam agreed and sent the appointment letter, adding that the country in question, i.e., the administration of its mission, was in the charge of the Sulayhid, who was also ordered to make some arrangements for Oman, which had at that time no mission. In 469/1076, the Sulayhid is charged with the government of the city of Oman. In 476/1083, the Sulayhid suggested appointment of Marzuban bin Ishaq in India and Ibrahim bin Ismail in Oman, which al-Mustansir billah agreed. In 481/1088, Marzuban died and his son Ahmad was recommended. In Oman, Ibrahim turned to commerce and neglected the mission, thus Hamza was recommended to succeed him.
Ahmad al-Mukarram died in 484/1091 and his wife Sayyida Hurrat al-Malika Arwa (477-532/1084-1138) then began to govern on behalf of Mukarram's minor son, Ali Abd al-Mustansir. When he too died, Sayyida Arwa took up the reins of administration of the state and mission, and remained loyal to al-Mustansir. She however supported the Mustalian line after the death of al-Mustansir.
The Fatimid vizir Badr al-Jamali died in 487/1095, and was succeeded by his son, al-Afdal as vizir. The administration of Badr al-Jamali was especially associated with a great development of building and with the construction of new walls and gates round Cairo.
The longest Caliphate of Muslim history for 60 years and 4 months closed with the death of al-Mustansir on the 18th Zilhaja, 487/January 6, 1095 at the age of 67 years and 5 months. The Fatimid dai, al-Muayyad fid-din ash-Shirazi had composed a 'Diwan' (Cairo, 1949), in which he versified few couplets in favour of al-Mustansir as under:-
'I offer my soul to al-Mustansir billah for redemption, who wins victories with the help of the hosts of heaven.' (p. 201)
'It is by him only that the Koran can be explained and interpreted.' (p. 273)
'I confess that you are the countenance of God by which the servants' countenances are radiant.' (p. 201)