À cet emplacement du 12e arrondissement de Paris, les pères de la Doctrine chrétienne créent un couvent en 1677. En 1790, l'assemblée Constituante crée la commune de Bercy, transformant l'église du couvent en église paroissiale. Elle est démolie en 1821 parce qu'elle tombe en ruines. Un nouvel édifice est érigé en 1824 sur les plans de l'architecte André-Marie Châtillon (1782-1859), édifice dédié à Notre-Dame-de-la-Nativité. Il est incendié sous la Commune en 1871. C'est d'ailleurs la seule église de Paris à subir ce triste sort. Seuls les murs subsistent et l'architecte Antoine-Julien Hénard (1812-1887) va les utiliser pour bâtir une troisième église en 1873 : elle aura donc le même périmètre que la précédente. Si le démarrage de la reconstruction a été rapide, sa fin se fera attendre : les plafonds plats à compartiments ne seront achevés qu'au début du XXe siècle.
Pour compenser cette lenteur, la Préfecture de la Seine pourvoit l'édifice en remarquables tableaux religieux de l'époque classique. En conséquence, bien que l'église soit entourée de rues et presque noyée dans la circulation, sa visite vaut le détour : Charles de la Fosse, Jacques Stella, Daniel Hallé, Louis de Boullogne et Jean-Baptiste Pierre y ont chacun une toile (qui est souvent éclairée par une lampe dont l'effet n'est pas des plus heureux). À noter aussi la présence d'une rareté : une statue en feuille d'étain du Bon Larron, représentation unique en France, qui date de 1995.
L'architecture de l'église est celle des basiliques romaines antiques, style fréquent sous la Restauration.