In September 1190 both Richard and Philip arrived in Sicily. In 1189 King William II of Sicily had died. His heir was Richardís aunt Constance, later Queen Constance of Sicily, who was married to Emperor Henry VI, Holy Roman Emperor. But immediately after William's death, William's cousin, Tancred, rebelled, seized control of the island and was crowned early in 1190 as King Tancred I of Sicily. He was favoured by the people and the pope but had problems with the island's nobles.
Richard's arrival caused even more problems. Tancred had imprisoned William's widow, Queen Joan, who was Richard's sister, and did not give her the money she had inherited according to William's will. Richard demanded that his sister be released and given her inheritance. Meanwhile the presence of two foreign armies caused unrest among the people. In October, the people of Messina revolted, demanding that the foreigners leave the island. Richard attacked Messina and captured it in October 1190. After looting and burning the city Richard established his base in it. He remained there until March 1191 when Tancred finally agreed to sign a treaty.
Richard, Philip and Tancred signed the treaty during the same month. According to the treaty's main terms:
1) Joan was to be released; receiving her inheritance along with the dowry her father had given to the deceased William.
2) Richard and Philip recognized Tancredi as legal King of Sicily and vowed to keep the peace between all three of their kingdoms.
3) Richard officially proclaimed his nephew, the son of Geoffrey, Arthur of Brittany, as his heir, and Tancred promised to later marry one of his daughters to Arthur when he came of age (Arthur was only four years old at the time).
After signing the treaty Richard and Philip left Sicily. The treaty undermined England's relationships with the Holy Roman Empire and caused the revolt of Richard's brother John, who hoped to be proclaimed heir instead of their nephew. Although his revolt failed, John continued to scheme against his brother after this point.
During April Richard stopped on the Byzantine island of Rhodes to avoid the stormy weather. He left in May but a new storm drove Richard's fleet to Cyprus.