The monastic hospitaller order was founded following the First Crusade by the Blessed Gerard, whose role as founder was confirmed by a Papal bull of Pope Paschal II in 1113. Gerard acquired territory and revenues for his order throughout the Kingdom of Jerusalem and beyond. His successor, Raymond du Puy of Provence, established the first significant Hospitaller infirmary near to the Church of the Holy Sepulchre in Jerusalem. Initially the group just cared for those pilgrims who made it to Jerusalem but the order soon extended into providing an armed escort to pilgrims. The escort soon grew into a substantial force.

Together with the Knights Templar, who were formed later in 1119, they became one of the most powerful Christian groups in the area. The order came to distinguish itself in battles with the Muslims, its soldiers wearing a black surcoat with a white cross. By the mid-12th century, the order was clearly divided into military brothers and those who worked with the sick. It was still a religious order and had useful privileges granted by the Papacy, for example, the order was exempt from all authority save that of the Pope, and it paid no tithes and was allowed its own religious buildings. Many of the more substantial Christian fortifications in the Holy Land were the work of either the Templars or Hospitallers, at the height of the Kingdom of Jerusalem the Hospitallers held seven great forts and 140 other estates in the area. The two largest of these, their bases of power in the Kingdom and in the Principality of Antioch, were Krak des Chevaliers, and Margat, both located near Tripoli. The property of the Order was divided into priories, subdivided into bailiwicks, which in turn were divided into commanderies.

The rising power of Islam eventually pushed the Knights out of their traditional holdings in Jerusalem. After the fall of the Kingdom of Jerusalem (Jerusalem itself fell in 1187), the Knights were confined to the County of Tripoli and when Acre was captured in 1291 the order sought refuge in the Kingdom of Cyprus. Finding themselves becoming enmeshed in the politics of that kingdom, their Grand Master Guillaume de Villaret created a plan of acquiring their own temporal domain, selecting Rhodes to be their new home. His successor Fulkes de Villaret executed the plan, and on August 15, 1309 after over two years of campaigning, the island of Rhodes surrendered to the knights. They also gained control a number of neighboring islands, as well as the Anatolian ports of Bodrum and Castellorizon.

The Knights Templar were dissolved in 1312 and much of their property was given to the Hospitallers. The holdings were organized into eight tongues (one each in Provence, Auvergne, France, Italy, Aragon, Castile, Germany and England). The English prior at the time was Philip Thame, who acquired the estates allocated to the English tongue from 1330 to 1358. On Rhodes, now known as the Knights of Rhodes they were forced to become a more militarized force, fighting especially with the Barbary pirates. They withstood two invasions in the 15th century, one by the Sultan of Egypt in 1444 and another by Mehmed II in 1480, who after the fall of Constantinople made the Knights a priority target.

However in 1522 an entirely new sort of force arrived when 400 ships under the command of Suleiman the Magnificent delivered 200,000 men to the island. Against this force the Knights had about 7,000 men-at-arms, and the walls of the city. The resulting siege lasted six months, at the end of which the survivors were allowed to leave Rhodes and retreated to the Kingdom of Sicily. In exchange, the knights promised to leave Suleiman's minions in peace. It would not be a promise they would keep.

Knights of Malta