L'actuel XIIIe arrondissement de Paris se trouve juste au nord de l'ancienne gare batelière d'Ivry. À la fin du XVIIIe siècle, de nombreux établissements industriels s'y implantent, comme les raffineries ou les verreries. S'y ajoutent, à la fin du siècle suivant, des usines de production d'automobiles. La population du XIIIe arrondissement a donc été en augmentation constante tout au long du XIXe siècle. Il fallait un lieu de culte supplémentaire. À l'instar de beaucoup d'églises parisiennes, le Second Empire s'en chargea. Notre-Dame-de-la-Gare fut érigée entre 1855 et 1864, par l'architecte Claude Naissant (1801-1879). Le style choisi fut le roman de la fin du XIIe siècle.
De par ses petites fenêtres, Notre-Dame-de-la-Gare est une église sombre car la nef n'est éclairée que pour les offices. Le chœur, embelli de deux grandes toiles marouflées dues à Osterlind et d'une belle voûte étoilée se détache par sa lumière et attire le regard.
À noter que, au XXe siècle, la fréquentation de l'église a été allégée en faisant de la chapelle Saint-Jean-des-Deux-Moulins, située quelques rues plus loin, une église paroissiale.