À l’origine, l’église devait faire face à la rue de La Gauchetière et à la cité existante, mais la Ville refusa le zonage du terrain d’en face à titre de «parc public». Refus qui eut d’heureuses répercussions, puisque il est avantageux que la Cathédrale ouvre sur le boulevard René-Lévesque, grande artère du centre-ville.

La première pierre fut posée le 28 août 1870. Les travaux, qui se trouvaient interrompus chaque fois que l’on manquait de fonds, progressèrent très lentement. En 1878, l’édifice n’était pas encore couvert, et les quatre piliers attendaient le dôme. Deux événements marquèrent cette première période: la crise financière de 1875-1876 (qui entraîna l’arrêt des travaux deux ans plus tard); et la démission, le 11 mai 1876, de Mgr Ignace Bourget, qui fut immédiatement remplacé par son coadjuteur, Mgr Édouard-Charles Fabre.

L’arrêt des travaux dura sept ans au cours desquels Mgr Bourget se fit «quêteur» pour aider son successeur à résoudre les difficultés financières du diocèse. En dépit d’un grand âge et d’une santé précaire, Mgr Bourget visita quelque 150 paroisses. Cinq jours après sa mort, le 8 juin 1885, sa dépouille mortelle fut déposée dans un caveau de la Cathédrale inachevée. On y transporta les restes de Mgr Lartigue, exhumés de l’église Notre-Dame-de-la-Pitié.

La Cathédrale abritant le tombeau des évêques, il fallait en hâter l’achèvement, car la neige et le gel s’accumulaient, l’hiver, entre les murailles. Les travaux se poursuivirent pendant six ans, en grande partie grâce au dévouement du procureur de l’oeuvre de la Cathédrale, M. le chanoine Racicot, ainsi que des recettes du grand bazar de 1886: 27,000$.

Le dôme fut achevé en 1886. Au mois d’août de la même année, la haute croix de dix-huit pieds de hauteur, en fer forgé, pesant 1,600 livres, fut fixée à son sommet. (Elle fut remplacée, en 1958, par une croix en aluminium de vingt pieds de hauteur.)

Mgr Fabre inaugura la Cathédrale le jour de Pâques, soit le 25 mars 1894, 42 ans après l’incendie de l’ancienne Cathédrale. À Montréal, c’était le premier édifice à avoir coûté plus d’un million de dollars. Il dominait alors toutes les autres constructions. Les Montréalais étaient fiers de posséder, en Amérique, la seule réplique de la Basilique Saint-Pierre-de-Rome.

Les travaux n’étaient pas achevés pour autant. En effet, l’exécution des statues de la façade se poursuivit jusqu’en 1900, année où l’on procéda à l’installation du baldaquin.

Le 30 avril 1904, Mgr Paul Bruchési décréta l’établissement d’une paroisse-cathédrale qui inclurait des portions de territoire des paroisses Notre-Dame et Saint-Joseph.

En 1919, le pape Benoît XV, à la demande de Mgr Bruchési, conféra le titre de Basilique mineure à la Cathédrale Saint-Jacques-le-Majeur. En 1933, la splendide chapelle mortuaire des évêques fut inaugurée par Mgr Georges Gauthier, cinquième évêque et troisième archevêque de Montréal.

Enfin, la Cathédrale subit une importante transformation entre 1955 et 1960. Le cardinal Paul-Émile Léger avait organisé, à cette fin, une opération de levée de fonds. C’est également à la demande du cardinal Léger que le pape Pie XII conféra à la Basilique le nouveau vocable de Marie-Reine-du-Monde.

Le 20 août 1951, Mgr Giovanni-Battista Montini, futur pape Paul VI, visita la Cathédrale. Le 31 août 1969, y entra le cardinal Karol Wojtyla, futur pape Jean-Paul II. On ne savait pas, alors, que le 10 septembre 1984, il reviendrait en cette même Cathédrale et serait le premier pape à visiter le Canada.