Ménilmontant jako malá ves patřila do farnostiSaint-Jean-Baptiste de Belleville. Na počátku 19. století se počet obyvatel rychle zvyšoval a v roce 1823 nebo 1833 byla postavena dřevěná kaple Notre-Dame-de-la-Croix, která byla v roce 1858 změněna na farní kostel. Protože kvůli rostoucímu počtu obyvatel nemohla stavba dostačovat, byla zbořena a nahrazena současným kostelem. Stavební práce začaly v roce 1863 a byly definitivně dokončeny až roku 1880, ale kostel sloužil bohoslužbám už od roku 1869. Stavba byla přerušena Pařížskou komunou.
Projektem kostela byl pověřen architekt Louis-Jean-Antoine Héret (1821-1899), který navrhl pseudorománsko-gotický styl. Kostel se nachází na návrší, takže k hlavnímu portálu vede impozantní schodiště s 54 schody. Nad ním se tyčí 78 metrů vysoká zvonice. Hlavní fasáda je členěná do tří pater. Dolní část tvoří tři obloukové portály s tympanony a archivoltami. Na středním portálu je znázorněno Snímání z kříže, na pravém útěk do Egypta a na levém Panna Marie v chrámu. Druhá úroveň průčelí tvoří rozeta, nad kterou stojí socha Panny Marie.
Kostel Notre-Dame-de-la-Croix je třetí největší kostel v Paříži díky své délce 97 metrů, šířce 38 metrů a výšce klenby 20 metrů. Hlavní loď končí u chóru s chórovým ochozem. Boční lodě jsou oddělené obloukovými arkádami s mohutnými sloupy. Křížová klenba je inspirována gotikou a je vyrobena z litiny.
Vybavení
V chórovém ochozu se nacházejí malby Nanebevstoupení Páně, autor Pierre Claude François Delorme (1783–1859) a Josefova smrt, autor Jean-Jacques Lagrenée (1606–1688). Varhany z roku 1874 vytvořil Aristide Cavaillé-Coll.
