The siege of Palermo lasted for five months and was fiercely contested. Palermo was one of the great Muslim cities, with a population of around 100,000, and was renowned as a centre of culture and trade. The Arabs were well prepared, with the city strongly fortified and the harbour protected by chains and towers. They were determined to defend their capital city to the best of their abilities. But among the population morale was low due to the earlier Norman victories.

Roger’s army was joined outside Palermo by Robert’s fleet of 60 ships. Their combined force consisted of knights, possibly over 1,000, together with infantry, siege engines and the equipment necessary for storming a city. The Norman ships, which were moored away from the harbour, were shortly put to the test by an Arab fleet sailing in towards Palermo. The Normans gained the initiative in the ensuing battle, with the Arab ships fleeing into the harbour. After they had entered, the defensive chain was put across the harbour’s mouth but several Norman ships in close pursuit crashed through the barrier, causing damage to the Arab fleet. Palermo was now completely surrounded with supplies to the city cut off.

At first the land battle was concentrated upon the citadel, the heavily fortified El-Kassar (Cassaro) district on the high ground. Roger led the attack, putting a third of the city’s walls under siege. Amid fierce fighting, javelins and arrows flew down from the ramparts on the attackers while Roger armed his infantry with bows and slings with which to return the fire. The Arabs made sorties outside the walls, which were defeated by the Normans who otherwise made little progress. Meanwhile conditions inside the city deteriorated rapidly through sickness and a lack of food. Leaving Roger to continue the main assault, Robert led an attack on the less well-defended Khalessah (Kalsa) district, down by the harbour, described by the chronicler Malaterra as follows:

Skilfully assembling machines and ladders for scaling the walls, the duke secretly entered the orchards with 300 knights to attack the city from the other side, namely the side where the ships lay, and instructed his brother by all means to do the same from his side. When the signal was given, they rushed in without hesitation and with great clamour to carry out what they had planned. All the citizens, rushing to arms, were terrified by the noise of the tumult and hastened to their own defence. In the process they carelessly left empty that part of the wall that normally had the fewest guards. There the wall was breached by Guiscard’s forces, which had placed ladders against it. Thus they took the outer city and opened the gates with iron bars so their allies could enter. The duke and the count and the entire army camped inside the city walls.

Once the Normans were established within the walls, the Arabs realised that the city was lost. But despite heavy casualties they were still in a strong position, in command of the citadel, and they decided to negotiate. They called a truce and offered to accept Norman rule, paying tribute, as long as their personal safety and freedom to follow their religion were guaranteed. These terms were accepted by Robert, who saw the advantages of avoiding a long and debilitating siege. It was the beginning of a new phase in Norman–Arab relations. While there were many more battles to come in other parts of Sicily, in the capital Palermo the interests of Muslim citizens were protected by the government. A surprising alliance had been born between Christians and Muslims.

In January 1072 the Normans formally took control of Palermo. They entered the city led by Robert Guiscard, his wife Sichelgaita and Roger, followed by other leading knights. They celebrated Mass at the basilica of Santa Maria, which had been rapidly reconverted from a mosque, taken by the reinstated Greek archbishop Nicodemus. Remains of the ancient basilica can be found in the modern cathedral.

Robert, having divided the Sicilian territories they had won between himself and Roger, remained in Palermo throughout the summer, establishing a garrison and strengthening fortifications. Repairs were made to the fort known as Castellammare (meaning ‘sea castle’) located at the harbour’s mouth. The Normans chose the highest part of the citadel for their base. Robert started work on the castle complex, which had been an Arab fort, building a walled perimeter on the high ground. A Norman governor was appointed to run the city’s administration, which was superimposed upon the existing Arab system. He retained the Arab title of emir, or ammiratus in Latin. This was Robert’s last contribution to the conquest of Sicily, for after he returned to Apulia in the autumn, he never returned to the island.