En 1840, la construction de la gare de l'Ouest (future gare Montparnasse) développe le village de Vaugirard et multiplie la population. Le petit édifice cultuel qui s'y trouve est insuffisant pour accueillir les fidèles. Vers 1845, une chapelle de secours, rattachée à l'église Saint-Lambert, est bâtie en bois.
Elle devient paroisse en mars 1848, puis est agrandie en 1858 et 1865.
D'abord dédiée à Notre-Dame de l'Assomption de Plaisance, elle change de dédicace en 1861 quand le village de Vaugirard est intégré à la capitale. Elle est alors dédiée à Notre-Dame de Plaisance.
La population continue de s'accroître. Un nouveau vicaire, le dynamique père Soulange-Bodin, est nommé en 1884. Il a la fibre sociale. Le développement d'organismes de charité au sein de foyers ouvriers miséreux ne lui suffit pas. Il veut faire bâtir une nouvelle église et lance une souscription nationale.
Selon ses vœux, l'édifice devra dégager une atmosphère familière aux ouvriers (voir plus bas).
Érigé sur un nouveau terrain, cet édifice est construit à partir de 1897 par l'architecte Jules Astruc (1862-1935), qui bâtira quelques années plus tard l'église Saint-Hippolyte dans le 13e arrondissement de Paris.
La nouvelle église est inaugurée en 1902.
L'intérieur de Notre-Dame-du-Travail-de-Plaisance est déconcertante. On pourrait se croire dans un grand hangar tant les poutres métalliques frappent par leur omniprésence. À cet égard, elle rappelle quelque peu les églises Saint-Jean-de-Montmartre et Saint-Eugène.
Néanmoins, les œuvres d'art y abondent et affichent par endroits un style Art nouveau.
Les chapelles latérales sont ornées de toiles célébrant les métiers ouvriers, tandis qu'une intéressante statue de Notre-Dame du Travail, réalisée en 1898 par un artiste de la paroisse, Joseph Lefèvre, trône dans la chapelle de la Vierge, entourée d'une grande peinture de Félix Villé.