El origen de esta orden es un tema en que los eruditos no se ponen de acuerdo; ha dado origen a leyendas ficticias y a peligrosas conjeturas. Sin lugar a dudas, el fundador fue un tal Gerald o Gerard, cuyo lugar de nacimiento y apellido se han investigado en vano. Por otra parte, su título de fundador está autentificado por un documento contemporáneo, la Bula de Pascal II, fechado en 1113 y dirigido a "Geraudo institutori ac praeposito Hirosolimitani Xenodochii". Ciertamente, este no fue el primer establecimiento de su clase en Jerusalén. Aún antes de las Cruzadas, los mesones eran indispensables para albergar a los peregrinos que acudían en tropel a los Lugares Santos y, al principio, los hospitia o xenodochia no eran otra cosa. Pertenecían a diferentes naciones; se habla de un hospicio fráncico en la época de Carlomagno.  se dice también que el hospicio húngaro data de la época del Rey San Esteban (año 1000). Sin embargo, el más famoso fue un hospicio italiano creado aproximadamente en el año 1050 por los mercaderes de Amalfi, quienes en esa época tenían relaciones comerciales con Tierra Santa. Se ha tratado de conectar el origen de los Hospitalarios de San Juan con esa fundación, pero es obvio que los Hospitalarios tenían a San Juan Bautista por patrono, mientras que el hospicio italiano estaba dedicado a San Juan de Alejandría. Además, los primeros adoptaron la Regla de San Agustín, mientras el segundo ejerció la regla Benedictina.  Como la mayoría de las casas similares de ese tiempo, el hospicio de Amalfi dependía de un monasterio; en cambio, el de Gerard fue autónomo desde el principio. Antes de las Cruzadas, el hospital italiano decayó, sostenido únicamente por limosnas recolectadas en Italia; pero Gerard se benefició con la presencia de los cruzados y la gratitud de éstos hacia su hospitalidad, que le valieron la adquisición de territorios e ingresos no sólo en el nuevo reino de Jerusalén, sino en Europa –Sicilia, Italia y Provenza. En las donaciones que quedaron registradas no se menciona a los enfermos, sólo a los pobres y a los extranjeros. Desde este punto de vista, el hospicio de Gerard no difería de otros, y su epitafio define su trabajo:

   Pauperibus servus, pius hospitibus . . . . Undique collegit pasceret unde sous.

    Gracias a los recursos acumulados por Gerard, su sucesor Raymond de Provenza (1120-60) erigió edificios más espaciosos cerca de la iglesia del Santo Sepulcro y, de ahí en adelante, el hospicio se convirtió en un hospital atendido por una comunidad de gente de hospital, en el sentido moderno de la palabra.

    Por lo tanto, para ser exactos, los Hospitalarios de Jerusalén nacieron con Raymond de Provenza, autor de la regla (que establece sólo su conducta como religiosos y enfermeros, sin mencionar lo de caballeros). Dicha regla establece, principalmente, que el hospital mantendrá permanentemente, y a su propia cuenta, a cinco médicos y tres cirujanos. Los hermanos debían realizar las funciones de enfermeros. Aproximadamente en 1150, un peregrino calculó el número de enfermos que recibían cuidados en 2000, una cifra evidentemente exagerada, a menos que incluyera a las personas hospedadas durante todo el año. Raymond continuó recibiendo donaciones, lo que le permitió complementar su fundación con una segunda innovación. Para acompañar, y defender cuando fuera necesario, a los peregrinos que llegaban y partían, sufragó el costo de una escolta armada, que con el tiempo se convirtió en un verdadero ejército formado por caballeros reclutados entre los cruzados de Europa, quienes servían como caballería pesada  y turcoples reclutados entre los nativos de sangre mixta, quienes hacían las funciones de caballería ligera armados a la usanza turca. Con esta innovación se originaron los grados militares más antiguos de la orden: el de mariscal, para comandar a los caballeros, y el de copler para dirigir a los turcoples. Posteriormente, los grandes maestres mismos participaron en batallas. Gosbert (hacia 1177), quinto sucesor de Raymond, se distinguió como hombre de armas, y Roger de Moulins pereció gloriosamente en el campo de batalla (1187). De esta forma, la Orden de San Juan se convirtió imperceptiblemente en una orden militar, sin perder su carácter hospitalario. Los estatutos de Roger de Moulins (1187) tratan exclusivamente sobre el servicio a los enfermos; la primera mención acerca del servicio militar aparece en los estatutos del noveno gran maestre, Alfonso de Portugal (aprox. 1200). En estos se hace una marcada distinción entre los caballeros seculares, externos a la orden, quienes servían sólo por un tiempo, y los caballeros declarados, unidos a la orden mediante un voto perpetuo, y poseedores de los mismos privilegios espirituales que los otros religiosos. De ahí en adelante, la orden nombraba dos clases de miembros: los hermanos militares y los hermanos enfermeros. Los hermanos capellanes, a quienes se les confiaba el divino servicio, formaban una tercera clase.

La Orden de San Juan se convirtió en una orden mixta, en tanto que la Orden de los Templarios era puramente militar al principio, y en este punto puede reclamar prioridad, a pesar de las aseveraciones contrarias de los hospitalarios. Los Templarios seguían otra regla monástica y vestían un hábito diferente: el hábito blanco de los cistercienses (cuya regla obedecían) con una cruz roja, mientras que los hospitalarios usaban el manto negro con una cruz blanca. Cuando iban a la guerra, los hermanos caballeros vestían sobre su armadura un sobretodo rojo con una cruz blanca. Estos dos grupos que se emularon desde el principio pronto se convirtieron en rivales, y dicha antipatía tuvo mucho que ver con el rápido declive del Reino de Jerusalén. Desde otros puntos de vista, ambas órdenes tenían el mismo rango en la iglesia y en el estado; eran reconocidas como órdenes regulares y el Papa les concedía grandes privilegios, absoluta independencia de cualquier autoridad espiritual y temporal (salvo la de Roma), exención de diezmos, con derecho a tener sus propias capillas, clero y cementerios. A ambas se les asignó la defensa militar de Tierra Santa, y las más formidables fortalezas del país, cuyas espléndidas ruinas aún existen, fueron ocupadas por alguna de las dos (Rey, "Monument de l'architecture militaire des Croisés", París, 1865). En el campo de batalla compartían los puestos más peligrosos, tomando por turnos la vanguardia y la retaguardia.

La historia de los Hospitalarios de Jerusalén está relacionada con la del Reino Latino del mismo nombre, con el que compartía la prosperidad y la adversidad. Cuando el reino se encontraba en su esplendor, los Hospitalarios poseían no menos de siete fortalezas, algunas situadas en la costa, otras en las montañas; entre ellas, Margat y Krals, en el territorio de Trípoli, son las más famosas. Disfrutaban de los ingresos provenientes de más de ciento cuarenta estados (casalia) de Tierra Santa. En cuanto a sus posesiones europeas, un escritor del siglo XIII les acreditó cerca de 19,000 casas o fincas. Fue necesario organizar una administración financiera para asegurar el cobro regular de los ingresos provenientes de estas posesiones tan dispersas. Esta fue la tarea de Hugo de Ravel, décimo séptimo Gran Maestre de Tierra Santa (hacia 1270). Las tierras unidas a una sola casa fueron puestas bajo el control de un caballero de la orden, quien al principio fue llamado preceptor pero luego tomo el título de comandante. Este oficial estaba encargado de recolectar las rentas, una proporción de las cuales servía para sostener a su comunidad, formada por un capellán y algunos hermanos; la otra parte estaba destinada a las casas de Tierra Santa. Esta última consistía en un impuesto anual e invariable llamado "Responsions".

    Gracias a estos recursos traídos de Europa, la orden pudo sobrevivir a la caída del Reino de Jerusalén, que implicó la pérdida de todas sus posesiones en Asia. Tras la captura de Jerusalén por parte de Saladino (1187), la Orden Hospitalaria pudo conservar solamente las posesiones que tenía en el Principado de Trípoli, las cuales perdió un siglo más tarde por la caída de Acre (1291). Sus miembros fueron obligados a buscar refugio, bajo las órdenes de su gran maestre, Jean de Villiers, en el Reino de Chipre, donde ya tenían algunas posesiones. El Rey Amaury les asignó como lugar de residencia el pueblo costero de Limasol. Al convertirse en isleños, los Hospitalarios se vieron obligados a modificar sus artes de guerra. Equiparon flotas para pelear contra los musulmanes en el mar y para proteger a los peregrinos, quienes no cesaban de visitar los Lugares Santos. Pero fue principalmente la conquista de la isla de Rodas, por el Gran Maestre Foulques de Villaret, lo que produjo una completa transformación de la orden.