In 1166, Margaret appealed to her other cousin, Rotrou, Archbishop of Rouen, to send her a family member to aid and support her in government. Coincidentally, Stephen was at that moment preparing to go on crusade to the Holy Land and so decided to visit Palermo, the capital of Sicily, for a few months. There he ended up staying for two years. He was very young at the time, described as puer and adolescens by William of Tyre, and may have still been in his teens. Nevertheless, in November, Margaret appointed him chancellor. His appointment was resented by the local nobility. His chancellorship was noted, according to Hugo Falcandus, in that "he never allowed powerful men to oppress their subjects, nor ever feigned to overlook any injury done to the poor. In such a way his fame quickly spread throughout the Kingdom... so that men looked on him as a heaven-sent angel of consolation who had brought back the Golden Age". The opinion of Falcandus probably coincides better with that of the lower classes than Stephen's fellow aristocrats.
In 1167, Margaret had Stephen elected as archbishop of Palermo, the highest ecclesiastic office in the land. He was ordained by Romuald, Archbishop of Salerno, only days before his elevation and it deeply rankled the old noblesse. Romuald and Richard Palmer, bishop of Syracuse, both candidates for the vacant see of Palermo themselves, were strongly opposed. But Stephen's greatest opponents was Matthew of Ajello, a notary whom he had offended the year previous. Stephen went so far as to try and seize Matthew's mail, but nothing indicating conspiracy was ever proven against the notary. Stephen was never consecrated, perhaps because had not attained the canonical age of thirty. In that year as well, Henry, Count of Montescaglioso, the queen's brother, returned from the peninsula on the counsel of his friends, who had goaded him into making a complaint to his sister about the rank of Stephen. Stephen won Henry over, for a while, but rumours of an affair between Stephen and Margaret was enough to push him into a conspiracy. Most of the Moslem staff of the palace and the eunuchs were involved in the plots and, on 15 December, Stephen promptly moved the court to Messina, to where he had implored his nephew Gilbert, Count of Gravina, to go with an army. The plotters, led by Matthew of Ajello and Gentile, Bishop of Agrigento, went to Messina, but Henry, for reasons unknown, gave them up to a local judge. At a meeting of the entire court, Gilbert accused Henry of treason and the latter was imprisoned in Reggio Calabria. By allowing Matthew to go free, however, Stephen prepared the way for future plots against his life.
Deposition and exile by a conspiracy
In March 1168, Stephen and his entourage, including the king, William II, and queen regent, arrived in Palermo, where the conspirators had already arrived. This time, Matthew was imprisoned and Gentile fled. He was arrested in Agrigento. But, though the Arabs of Palermo had been soothed, the Messinan Greeks had been riled by the past months and a rebellion consequently broke out in that city. There, a mob commandeered some ships and sailed to Reggio, there to force the release of Henry of Montescaglioso. After Henry's arrival in Messina, Odo was arrested and brutally executed and all the Frenchman of the city massacred: an inglorious prélude to the more widespread Sicilian Vespers of 1282. Stephen prepared an army and was ready to march on Messina when the young king postponed the campaign on astrological grounds. Matthew of Ajello, from prison, had organised the rebellion in Palermo and, seeing his opportunity, struck. And it was rumored that William II was murdered and the chancellor planned to marry his brother to Princess Constance, who was confined to Santissimo Salvatore, Palermo as a nun from childhood due to a prediction that "her marriage would destroy Sicily", to claim the throne, despite the existence of Henry younger brother of William. Stephen was finally forced to flee. The chancellor-archbishop was forced to take refuge in the campanile, there he held out until offered terms. In return for his safety, he agreed to embark at once for the Holy Land. He was deposed as archbishop and Walter of the Mill was elected to replace him. Gilbert of Gravina and his family were forced to do the same and they all left for the Kingdom of Jerusalem. With the attempt of Margaret to recall him in vain, he arrived in Jerusalem the summer of 1169 and soon fell ill and died. According to William of Tyre, "he was buried with honour in Jerusalem in the chapter-house of the Temple of the Lord."
