En 1907, la paroisse Saint-Michel comptait près de cent mille habitants. Elle était de ce fait devenue trop importante pour un seul clocher. Monseigneur Amette, archevêque de Paris, prit la décision de créer une nouvelle paroisse à la demande du curé de Saint-Michel, l’abbé Baston, et de lui donner le nom de Joseph, le prénom civil du pape de l’époque, suivi du nom du quartier, Épinettes.

L’église est placée sous le patronage de saint Joseph mais aussi de saint Clément, quatrième pape après saint Pierre et patron des ouvriers, nombreux dans le quartier au début du 20ème siècle, notamment dans le métal, en raison des activités ferroviaires des usines Gouïn. L’église est la première bâtie à Paris après la loi de la séparation de l’Église et de l’État de 1905. Construite en briques et béton armé par l’architecte Placide Thomas, elle a la forme classique d’une croix d’inspiration byzantine.

La bénédiction de la première pierre eut lieu le 19 mars 1909, en la fête de saint Joseph, et sa consécration par le cardinal L. Amette, le 24 mai 1910. L’intérieur de l’église est éclairé par une verrière zénithale octogonale et par de nombreuses verrières hautes et basses ornées de figures de saints et de saintes commandées à L.-S. Chanussot en 1912 et offertes par des paroissiens, par l’asile de l’Ouest, par le clergé ou en souvenir de la mission de 1911. Les cartons des Saintes Cécile, Marguerite et de Saint Michel transperçant le dragon sont à l’évidence inspirés des figures peintes par Raphaël, conservées au musée du Louvre et à Bologne.

Dans les années 1990, une série de travaux importants a été réalisée, donnant à l’église son aspect actuel.