Au XIXe siècle encore, la ville actuelle de Paris, en dehors du Paris médiéval, n'était qu'une suite de petits bourgs dans la campagne. En 1824, le village des Batignolles comptait cinq mille habitants et dépendait de Clichy. On décida de construire une église ; une souscription fut lancée. La petite somme récoltée ne permit que l'érection d'une chapelle terminée en 1829. Mais la population continua de s'accroître. Le village devint la commune indépendante de Batignolles-Monceau.
Pour des besoins cultuels évidents, il fallut agrandir la chapelle. L'architecte Paul-Eugène Lequeux (1806-1873) fut chargé des travaux. Respectant la forme en croix latine, il fit ajouter les deux bas-côtés, le transept et le chœur. Le tout s'acheva en 1851. En 1860, la commune de Batignolles-Monceau est rattachée à Paris.
L'édifice s'inspire de la basilique romaine antique. Son porche ressemble à celui d'un temple grec. L'intérieur porte la marque des églises construites sous la Restauration : Sainte-Marie-des-Batignolles est une église sobre, presque sévère. Heureusement, un plafond plat à compartiments peints et un superbe chœur, à la mode du XIXe siècle, avec un magnifique retable sculpté, viennent casser cette sobriété et embellir l'édifice.