He wanted to build it on three hundred marble columns. He was told that such a number could not be obtained and that if he insisted on his decision, he would leave nothing for the Christians to build their temples. He hesitated between proceeding with his project and not depriving other denominations of their religious right to build temples.

The Christian engineer mentioned earlier, named Ibn al-Katib al-Farghani, was knowledgeable and skilled in engineering and construction. He had been imprisoned on false charges. When he learned of Ibn Tulun's decision and hesitation, he wrote to him from prison that he could complete his project and that he needed no more than two columns to serve as the qibla.

Ibn Tulun summoned him. His hair had grown so long that it fell over his face. He asked him to explain his plan. He drew the mosque as he envisioned it, very similar to the Mosque of Samarra. Ibn Tulun was greatly impressed, ordered his release, gave him a robe, and allocated one hundred thousand dinars for his project, telling him to spend what he needed and that they would release more to him later. Ibn Tulun ordered that the mosque be built of brick and plaster and forbade the use of any flammable materials, saying, "My desire in this is that if Fustat is destroyed by water or fire, my mosque will be safe and remain even if all else is destroyed."

When the construction of the mosque was completed, he began to decorate it. He whitewashed it, hung long brass lamps with brass chains, and inscribed verses from the Noble Quran on its walls, most of which are still visible today. He furnished it with carpets and brought it chests of books and readers and jurists. It is said that he himself repaired the qibla and the minaret, making them separate from the mosque by a portico attached to the mosque, and separating the minaret from a second outer courtyard. Some of this minaret has been demolished, but anyone who sees it cannot help but marvel at its grandeur. It is said that the minaret had a staircase. The mosque's builder built a large gate called the Great Gate and provided a door to the mosque from a window in its qibla wall near the mihrab. The minbar was decorated with curtains. In that house, there were couches and rich carpets. Ibn Tulun would stay in that house when he went to Friday prayers, as it faced the palace and the square. He would sit there, renew his ablutions, and change his clothes. In its place today is the market of the mosque.

Whoever visits this mosque today will find it in ruins. The government has repeatedly used it as housing for pilgrims and the poor. They built in its arches and blocked them. Some of those arches have been demolished.