In 1657, the Roman Catholic Sulpician Order arrived in Ville-Marie, now known as Montreal; six years later the seigneury of the island was vested in them. They ruled until 1840. The parish they founded was dedicated to the Holy Name of Mary, and the parish church of notre-dame was built on the site in 1672. The church served as the first cathedral of the Diocese of Montreal from 1821 to 1822.
By 1824 the congregation had completely outgrown the church, and Jame O'Donnell, an Irish-American Protestant from New York, was commissioned to design the new building. O'Donnell was a proponent of the Gothic Revival Architectual Movement, and designed the church as such.
He is the only person buried in the church's crypt. O'Donnell converted to Catholicism on his deathbed perhaps due to the realization that he might not be allowed to be buried in his church. The sanctuary was finished in 1830, and the first tower in 1843. On its completion, the church was the largest in North America. A new pipe organ was built in 1858 by Samuel Russel Warren.
The interior took much longer, and Victor Bourgeau, who also worked on Montreal's Mary Queen of the World Cathreall, worked on it from 1872 to 1879. Stonemason John Redpath was a major participant in the construction of the Basilica. Because of the splendour and grand scale of the church, a more intimate chapel, Chapelle du Sacré-Coeur (Chapel of the Sacred Heart), was built behind it, along with some offices and a scaristy.
It was completed in 1888. In 1886 Casavant Freres began building a new 32-foot pipe organ at the church, completing it in 1891. It was notably the first organ with adjustable-combination pedals to be operated by electricity.