I mitten av 1100-talet inrättades en benediktinerkloster i Jerusalem av köpmän från Amalfi. Cirka 30 år senare grundades ett sjukhus bredvid klostret för att ta hand om sjuka och fattiga pilgrimer. Efter framgången med första korståget 1099 utökade broder Gerard (eller Gerald), sjukhusets överordnade, sjukhuset och inrättade ytterligare sjukhus längs vägen till det heliga landet.
Den 15 februari 1113 utnämndes beställningen formellt till Hospitallers of St. John of Jerusalem och erkändes i en påvlig tjur som utfärdades av påven Paschal II.
Knights Hospitaller var också känd som Hospitalers, the Order of Malta, the Knights of Malta. Från 1113 till 1309 var de kända som sjukhus i St John of Jerusalem; från 1309 till 1522 gick de efter riddarnas ordning; från 1530 till 1798 var de suveräna och militära ordningen för riddarna på Malta; från 1834 till 1961 var de Knights Hospitaller of St. John of Jerusalem; och från 1961 till nutid är de formellt kända som den suveräna militära och sjukhusordern av St. John av Jerusalem, av Rhodos och Malta.
1120 efterträdde Raymond de Puy (a.m. Raymond av Provence) Gerard som ordförande. Han ersatte den benediktinska regeln med den augustinska regeln och började aktivt bygga upp ordermaktbasen och hjälpte organisationen att skaffa land och rikedom. Möjligen inspirerad av templarna, började sjukhusledarna ta upp vapen för att skydda pilgrimer såväl som deras sjukdomar och skador. Hospitaller Knights var fortfarande munkar och fortsatte att följa sina löften om personlig fattigdom, lydnad och celibat. Beställningen omfattade också kapellän och bröder som inte tog upp vapen.
De västra korsfararnas skiftande förmögenheter skulle också påverka sjukhusledarna. 1187, när Saladin fångade Jerusalem, flyttade Hospitaller Knights sina huvudkontor till Margat, sedan till Acre tio år senare. Med Acre fall 1291 flyttade de till Limassol på Cypern.
År 1309 förvärvade sjukhusledarna ön Rhodos. Den stora mästaren av ordern, som valdes för livet (om den bekräftades av påven), styrde Rhodos som en oberoende stat, mynta och utöva andra suveränitetsrättigheter. När riddarna av templet spriddes anslöt sig några överlevande tempelränare till Rhodos. Riddarna var nu mer krigare än "gästgivare", även om de förblev ett klosterbrödraskap. Deras aktiviteter inkluderade marinkrig; de beväpnade fartyg och startade muslimska pirater och tog hämnd på turkiska köpmän med egna piratkopiering.
1522 avslutades sjukhusstyraren över Rhodos med en beläggning på sex månader av den turkiska ledaren Suleyman den magnifika. Riddarna kapitulerade den 1 januari 1523 och lämnade ön med de medborgare som valde att följa dem. Hospitallersna var utan bas fram till 1530, då den heliga romerska kejsaren Charles V ordnade för dem att ockupera den maltesiska skärgården. Deras närvaro var villkorad; det mest anmärkningsvärda avtalet var presentationen av en falk till kejsarens viceroy på Sicilien varje år.
1565 visade stormestern Jean Parisot de la Valette utmärkt ledarskap när han stoppade Suleyman den magnifika från att lossna riddarna från deras maltesiska högkvarter. Sex år senare, 1571, förstörde en kombinerad flotta av riddarna på Malta och flera europeiska makter den turkiska flottan i slaget vid Lepanto. Riddarna byggde en ny huvudstad på Malta för att hedra la Valette, som de kallade Valetta, där de konstruerade storslagna försvar och ett sjukhus som lockade patienter från långt bortom Malta.
Hospitallers hade återvänt till sitt ursprungliga syfte. Under århundradena gav de gradvis upp krigföring till förmån för medicinsk vård och territoriell administration. 1798 förlorade de Malta då Napoleon ockuperade ön på väg till Egypten. För en kort tid återvände de under regi av Amiensfördraget (1802), men när Parisfördraget 1814 gav skärgården till Storbritannien, gick sjukhusledarna en gång till. De slutligen bosatte sig permanent i Rom 1834.
Även om adel inte var skyldig att gå med i klosterordningen, var den skyldig att vara en sjukhusvittare Knight. Allteftersom tiden gick blev detta krav strängare, från att bevisa adel för båda föräldrarna till det hos alla morföräldrar i fyra generationer. En mängd riddarliga klassificeringar utvecklades för att rymma mindre riddare och de som gav upp sina löften att gifta sig, var dock fortfarande kopplade till beställningen. Idag är det bara romersk-katoliker som kan bli sjukhus, och de styrande riddarna måste bevisa adeln för sina fyra morföräldrar i två århundraden.
Efter 1805 leddes ordern av löjtnanter tills stormästarnas kontor återställdes av påven Leo XIII 1879. 1961 antogs en ny konstitution där ordningens religiösa och suveräna status exakt definierades. Även om beställningen inte längre reglerar något territorium, utfärdar den pass och den erkänns som en suverän nation av Vatikanen och vissa katolska europeiska länder.