Der Johanniterorden entstand nach der Eroberung Jerusalems durch das Heer des Ersten Kreuzzuges im Jahre 1099 als Orden vom Hospital des Heiligen Johannes zu Jerusalem (lateinischer Name: Ordo Hospitalis sancti Johannis Ierosolimitani). Die Ordensgemeinschaft wurde auch Ritterlicher Orden Sankt Johannis vom Spital zu Jerusalem genannt, die Ritter wurden als Johanniter oder Hospitaliter bezeichnet.
Nach dem Untergang der Kreuzfahrerstaaten wurde der Sitz des Ordens zunächst 1291 von Akkon nach Zypern verlegt und 1309 nach Rhodos. In der Zeit auf Rhodos wurden die Ritter auch Rhodesier genannt. Nach der Eroberung der Insel durch die Osmanen ließ sich der Orden nach mehreren Zwischenstationen 1530 in Malta nieder. So entstanden die heute üblichen Bezeichnungen Malteser beziehungsweise Malteserorden für den katholisch gebliebenen Hauptteil des Johanniterordens, dessen offizieller Name lautet: Souveräner Ritter- und Hospitalorden vom Heiligen Johannes von Jerusalem von Rhodos und von Malta. Im Jahr 1538, also fast zur selben Zeit, als der katholisch gebliebene Teil des Johanniterordens die Insel Malta erhielt, waren die Ritter der Johanniter-Ballei Brandenburg evangelisch geworden und damit entstand ein protestantischer Nebenzweig des Ordens, der bis heute Johanniterorden genannt wird.
Der Orden ging aus einem 1048 erstmals erwähnten Pilgerspital, dem Muristan hervor, das von Kaufleuten aus Amalfi bereits lange vor dem ersten Kreuzzug gestiftet worden war. Dieses war Johannes dem Täufer geweiht, wovon sich der Name Johanniter ableitet. Pilger stellten einen bedeutenden Wirtschaftsfaktor dar, weshalb Schutz und Pflege derselben mittelbar allen Anrainern des Mittelmeerraumes zugutekam. Die Versorgung der Kranken wurde durch Ordensbrüder übernommen.
Aus der Zeit um 1160 ist der Bericht des Pilgers Johannes von Würzburg überliefert:
Als Ordensgründer gilt der Selige Gerhard Tonque (um 1040–1120). Er war der Leiter der Spitalsbruderschaft, die das Pilgerhospital in Jerusalem betrieb, als der Erste Kreuzzug Jerusalem eroberte. In der Folgezeit gewann die Spitalsbruderschaft erheblichen Zulauf. Unter Raimund von Puy (1120–1160), der dem Ordensgründer nachfolgte, vollzog sich 1120 bis 1140 der Wandel von der Spitalbruderschaft zum geistlichen Ritterorden. Unter ihm weitete sich die Tätigkeit des Ordens von der Pflege und Beherbergung der Pilger schrittweise auch auf deren militärischen Schutz aus. Als Vorbild hierfür diente der junge Templerorden.
Nach Einnahme Akkons 1104 durch die Kreuzfahrer übernahmen die Johanniter als ihre Kommende ein Geviert südwestlich der großen Freitagsmoschee (zu der Zeit im Umbau/Abbruch für die neue Heilig-Kreuz-Kathedrale), das Ze'ev Goldmann als eine arabisch-fatimidische Karawanserei des 10. oder 11. Jahrhunderts identifizierte.
Im Jahre 1110 bestätigte Balduin I. von Jerusalem die Johanniter im Eigentum weiterer, ihnen gestifteter Bauten nördlich von Akkos Kreuzkathedrale. Auf die Schenkungen hin begannen zu Beginn des 12. Jahrhunderts die Johanniter ihre Kommende in Akko nördlich des ursprünglichen Gevierts des Hospitals. In den 1130er Jahren mussten beim Anbau des neuen Nordportals der Kreuzkathedrale benachbarte Johanniterbauten weichen, woraufhin die Ordensgemeinschaft den Standort nördlich der Kathedrale aufgab und Mitte des 12. Jahrhunderts seine Niederlassung weiter westlich um ein neues Ordenshaus erweiterte, was heute den Grand Manoir im Unterbau der heutigen Zitadelle darstellt. Älteste Nachricht dieses Baus stammt von 1141 aus der Zeit der Königin-Regentin Melisende von Jerusalem.
Als neue Nordseite des Hospitalhofes, südlich an einer Geschäftsstraße und nunmehr im Zentrum der sich beiderseits dieser Straße erstreckenden Kommende errichteten die Johanniter ihr Johannes dem Täufer geweihtes Gotteshaus, wenig westlich von der Kreuzkathedrale. Älteste Nachricht von dieser Johanniskirche stammt aus dem Jahre 1149.
Der Orden bestand damals aus Rittern, den Kirchendienst übernahmen Priester, mit der Krankenpflege waren auch nichtadelige Brüder betraut. Raimund selbst nannte sich noch Meister, der Titel Großmeister wurde erst 1267 von Papst Clemens IV. für Hugo von Revel bewilligt.
Zunächst trugen die Johanniter eine einfache schwarze Mönchskutte. Als der ursprüngliche Hospitaldienst immer mehr durch den bewaffneten Schutz von Pilgern und den Kampf in Kreuzzugsgebieten ergänzt wurde, trugen sie ab dem 13. Jahrhundert einen schwarzen Übermantel mit einem weißen Kreuz darauf, das in acht Spitzen endete. Neben den adeligen Ordensrittern dienten auch eine große Zahl Nichtadelige dem Orden. Die Hilfskräfte, die nicht dem Orden angehörten, wurden als „Sergeanten“ bezeichnet. Davon wurden die zum großen Teil nichtadeligen Sergeantenbrüder unterschieden, die die Ordensgelübde abgelegt hatten, aber nicht den Zugangsvoraussetzungen der Ritterbrüder genügten. Diese Sergeantenbrüder versahen den gleichen Dienst wie die Ritter, waren aber von Führungspositionen ausgeschlossen. Sie trugen eine andere Uniform und Ausrüstung, z. B. in der Frühzeit braune statt schwarze Mäntel.
Hatte der Orden bis dahin das Ziel, kranken Mitmenschen zu dienen, trat als zweiter Auftrag des Ordens die Bekämpfung des Unglaubens und der Schutz der Pilger hinzu. 1136 wurde den Johannitern erstmals eine Burg anvertraut, die im Jahr zuvor an der Straße von Askalon nach Jerusalem errichtete Burg Gibelin. In den 1140er Jahren wurden dem Orden weitere Festungen angedient. Graf Raimund II. von Tripolis verpflichtete sich ihm gegenüber, keinen Frieden ohne seine Zustimmung zu schließen. Imposante Zeugnisse der Geschichte des Johanniterordens im Heiligen Land sind die im 12. Jahrhundert errichtete Burg Belvoir in Israel, die 1142 übernommene Burg Krak des Chevaliers oder die 1186 in den Besitz der Johanniter gekommene Burg Margat (Qalaʿat al-Marqab) in Syrien. Bis 1187 erwarb bzw. baute der Orden insgesamt 25 Burgen in Outremer, davon 15 in Syrien und 10 im Königreich Jerusalem.
Ab Mitte des 13. Jahrhunderts wurde es üblich, dass die Ordenskämpfer in Kriegszeiten einen roten Mantel mit weißem Kreuz trugen. Die Johanniter trugen in ihren Siegeln zu dieser Zeit ein einfaches Kreuz in der Form des „Jerusalemer Kreuzes“, späterhin ein einfaches weißes Kreuz. In der Zeit von Rhodos wandelte sich diese Kreuzesform zu einem Kreuz mit eingekerbten Spitzen. Die aktuelle Form, die als Malteserkreuz bekannt ist, wurde tatsächlich erst in der Malteser Zeit zum typischen Emblem des Ritterordens. Seit 1262 war in den Statuten des Ordens festgelegt, dass nur Adelige als Ritter dienen durften, jedoch erst ab 1555 wurde Abkömmlingen von Familien muslimischen oder jüdischen Glaubens die Mitgliedschaft versagt.
Die Krankenversorgung verschaffte der Hospitalbruderschaft große Bekanntheit. Bereits am 15. Februar 1113 erließ Papst Paschalis II. das Privileg Pia postulatio voluntatis, in dem der Orden von der Pflicht der Zehntabgabe entbunden und unter päpstlichen Schutz gestellt wurde. Seine Besitzungen in Europa und in Outremer wurden ihm bestätigt. Auch war die Bruderschaft in der Wahl ihres Vorsitzes freigestellt. 1117 wurde auch das Hospital selbst unabhängig. Als Ordensregel wählten die Johanniter die Augustinusregel. Stiftungen vieler Adeliger aus allen Teilen Europas mehrten das Vermögen und wurden auch zur Einrichtung von Stationen und kleineren Hospitälern auf den Pilgerwegen verwendet. Bari, Otranto, Tarent, Messina, Pisa, Asti und Saint-Gilles (Südfrankreich) wurden erwähnt. Zugleich erhielt die Bruderschaft die päpstliche Anerkennung. Mit dem Privileg „Christianae fidei religio“ vom 21. Oktober 1154 wurde der Orden durch Papst Anastasius IV. aus der bischöflichen Jurisdiktion herausgehoben und als Orden direkt dem Papst unterstellt. Mitarbeiter des Ordens als dienende Brüder hatten das Gelübde des Gehorsams abzulegen, als Ritter oder Priester dienende Mitglieder zusätzlich die Gelübde von Keuschheit und Armut, wobei letzteres lediglich den Verzicht auf Privateigentum bedeutete.
Ordensritter übernahmen auch die Verwaltung des Ordensbesitzes außerhalb des Mittelmeerraumes. Die Erlöse aus den Besitzungen wurden zum Teil an den Orden selbst abgeführt, zum Teil ermöglichten sie die Versorgung der Ritter vor Ort als Pfründe. Durch dieses System wurde die materielle Versorgung von Rittern möglich, die als nicht erbberechtigte Söhne über kein eigenes Vermögen verfügten und die dadurch nicht mehr gezwungen waren, zwischen einer rein militärischen oder einer kirchlichen Laufbahn zu wählen. Diese Verwalter hatten ein großes Interesse daran, dass die aus der Pfründe erwirtschafteten Vermögen nicht abgezogen wurden, sondern in der Pfründe verblieben. Der Interessengegensatz zwischen Ordenszentrale und lokalen Verwaltungen blieb auch weiterhin stets ein wesentliches Problem des Ordens.