O’Donnell postanowił zaprojektować kościół w modnym wówczas w Anglii i Stanach Zjednoczonych stylu neogotyckim, przy tym dostatecznie obszerny, aby sprostać potrzebom 8-tysięcznej wówczas parafii. Podstawowe roboty budowlane wykonano w latach 1824–1829. O’Donnellowi nie dane było dożyć do całkowitego zakończenia prac. Zmarł w Montrealu w 1830 roku. Tuż przed śmiercią nawrócił się na katolicyzm i został pochowany w nowym kościele w krypcie, a jego grób został oznaczony tablicą. Kościół Notre-Dame był przez następne pół wieku największym kościołem Kanady i Stanów Zjednoczonych. Jego wczesny, neogotycki styl, wyrażający się w prostym rozplanowaniu nawy z galeriami i bliźniaczymi wieżami, zapoczątkował przełom stylistyczny w kanadyjskiej architekturze sakralnej. Budynek kościoła reprezentuje zarazem romantyczne, nieakademickie podejście do neogotyku, kontrastując pod tym względem z wybudowanymi w II poł. XIX w. dużymi anglikańskimi i katolickimi katedrami Kanady.