Церковь основана Рожером I в 1070 году на месте взятой им арабской крепости, прикрывавшей с юга подступы к Палермо, и была освящена в честь Иоанна Крестителя. Уже в конце XI века к церкви был пристроен госпиталь для прокаженных, отчего храм и получил своё нынешнее название. В конце XX века были удалены последующие барочные наслоения, и на сегодня Сан-Джованни-деи-Леббрози вновь является одним из наиболее характерных строений арабо-норманнского стиля.
Церковь представляет собой трёхнефную базилику с двускатной кровлей и тремя апсидами. Внешний вид строг и оживляется только арочными арабскими окнами. Пристроенная веком позже двухъярусная колокольня также имеет типично арабский вид — арочные оконные проёмы, вписанные в скупой резной узор из ложных арок, красный полусферический купол. Интерьер церкви, разделённый на нефы рядом колонн, также практически лишён убранства.