Sa nef centrale fut érigée sur les fondations d'une église plus ancienne au XIIIe siècle et servait comme église de l'Hôpital qui se trouvait à l'emplacement de l'actuel musée Granet. L'église était alors au service de l'ordre des Hospitaliers de Saint-Jean-de-Jérusalem, d'où son nom. Le chevet plat et le transept ne sont que légèrement postérieurs. Elle devient ensuite commanderie de Rhodes puis de Malte. Elle devient alors dépendance du grand prieuré de Saint-Gilles. On dit que c'est la ville d'Aix qui a vu sortir le plus de chevaliers de Malte.
En 1292, les Hospitaliers reçoivent l'autorisation de placer quatre cloches au sommet du clocher de l'église, ce qui indique que, dès cette époque, celui-ci devait déjà être d'une taille conséquente. Aujourd'hui, ce clocher compte 67 mètres de hauteur, ce qui en fait le point le plus haut de la ville d'Aix-en-Provence. Si l'on ajoute à cela ses caractéristiques gothiques, tout le rapproche de nombreux édifices religieux du Nord de la France par son aspect rigide et austère. Les estimations quant à sa date d'achèvement varient grandement. Si la tradition le situe en 1376, des recherches récentes tendraient davantage à le situer au milieu du XVe siècle. Dans un cas comme dans l'autre, on ne peut manquer de souligner l'audace architecturale de l'ouvrage totalement en contradiction avec les canons de son temps, que ce soient le portail de la cathédrale d'Aix, ou la chapelle d'Hélion de Villeneuve, ses contemporains.
La partie inférieure du clocher est montée sur un carré massif et épaulée par des contreforts. Le tout ne possède pas d'ouverture. Le premier étage, en revanche, possède quatre baies allongées dans le sens de la hauteur et abrite l'unique cloche. Au-dessus, la flèche est entourée de quatre clochetons et ajourée par huit lucarnes. Au Moyen Âge, le tout était couronné d'un épi de métal surmonté d'une croix latine. Celui-ci a été remplacé, en septembre 1755 par une croix de Malte, après un orage survenu en novembre 1754 qui avait abattu l'épi. La foudre s'y abat d'ailleurs régulièrement, ce qui implique la nécessité de rénover la flèche une à deux fois par siècle.
L'historien aixois Ambroise Roux-Alphéran a lu sur des pierres aujourd'hui déposées l'inscription « XPS [Christus] Rex venit in pace, Deus homo factus est » (« Le Christ-roi est venu dans la paix, Dieu s'est fait homme »), un message à la gloire du Christ.
La façade telle qu'on peut la voir aujourd'hui a été remaniée au XVIIe siècle, même si elle a été construite au XIIIe siècle. Le pignon qui la domine est surmonté d'une croix de Malte. Les tuiles mécaniques de la charpente sont clouées en raison de risques de vent qui pourraient les fragiliser. Jusqu'en 1906, il était possible de voir le ciel à travers les pignons, lorsqu'ils étaient ouverts.
Le détail architectural qui frappe le plus au regard de la façade est ces deux tours octogonales, hautes de trente-deux mètres, qui se dressent de part et d'autre de l'édifice. Elles sont percées de meurtrières étroites et surmontées d'une coiffe en pyramide. À leur sommet, un balcon les relie et surmonte une grande rose de 4 mètres de diamètre. La tour de gauche date de la construction du clocher, tandis que celle de droite a été réalisée en même temps que le balcon, en 1691.
Le portail, quant à lui, possède deux vantaux datés de la fin du XVIIe siècle ou du début du XVIIIe siècle. Ils étaient décorés à l'origine de croix de Malte, mais cette décoration a été supprimée. Au-dessus, on peut apercevoir deux gargouilles à tête de chien que l'on peut rapprocher des armoiries du prieur Jean-Claude Viany. La porte est divisée deux baies et au-dessus d'elles se trouve un tympan décoré de trèfles et d'arcs trilobés.
L'ensemble de la façade est restauré par l'architecte aixois Henri Révoil entre 1851 et 1858.
Le chevet plat de l'église peut être observé rue d'Italie. Une maison construite contre le mur obstruait jadis la grande fenêtre en tiers-point d'une hauteur de 11 mètres. C'est l'acquisition de cette maison par la municipalité d'Aix-en-Provence en 1855 qui permet la démolition et la restauration de l'ensemble tel qu'il se présentait à l'origine.