En 1290, d'après les récits de l'époque, un Juif parisien emprunta une hostie consacrée à une vieille dame, puis la profana à coups de couteau. Le sang du Christ en jaillit ! 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. À son tour, l'ordre des Carmes réformés fut gardien des lieux 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 l'Empereur, pour être affecté à l'église luthérienne de la capitale. Jusque-là, les chapelles des ambassades de Suède et du Danemark servait de lieux de réunion à cette église. Désormais, elle possédera son temple, 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.