D'après les récits de l'époque, en 1290, un Juif parisien emprunta une hostie consacrée à une vieille dame, puis la profana. Les coups de couteau en firent jaillir le sang du Christ ! Jetée au feu, elle resta intacte ! Le Juif fut brûlé vif. On édifia une chapelle (dite «des Miracles») à l'endroit où avait habité le condamné . Quatre ans plus tard, les frères de la Charité Notre-Dame s'y installèrent, invités par le roi Philippe le Bel. Ils acquirent plus tard quelques maisons voisines et, vers 1425, édifièrent le cloître médiéval que l'on voit toujours. Chapelle et cloître furent restaurés au fil du temps. L'ordre des Carmes réformés tint les lieux à son tour de 1633 à 1790. L'église actuelle a été construite à partir de 1755 sur les plans du frère dominicain Claude Navan (1697-1774) ou, selon d'autres sources, sous la direction de Jules Hardouin-Mansart de Sagonne (1711-1778). À la Révolution, tout est vendu. Le cloître devient un atelier de menuiserie ; l'église, un dépôt de sel.
En 1808, l'ensemble est racheté par la Ville de Paris, avec l'accord de Napoléon Ier, pour être affecté à l'église luthérienne de la capitale. Jusque-là cette communauté se réunissait dans les chapelles des ambassades de Suède et du Danemark. Désormais, elle possédera son sanctuaire, puis un second en 1843. L'église des Billettes sera enrichie par des dons (tableaux dans la sacristie). Au XIXe siècle, elle profitera de la protection de la duchesse Hélène d'Orléans.