Le responsable de la chapelle, le père Jean-Antoine Bernard, demande le 22 juin 1850 au ministère de la guerre, l'autorisation de reconstruire en plus grand la chapelle existante. Le 22 octobre 1850, le jour même où il quittait ses fonctions ministérielles, le général d'Hautpoul, ministre de la guerre, trouvant la demande trop imprécise, donne un accord de principe mais invite la commission du temporel à présenter un projet plus précis. Le 8 avril 1851, une nouvelle demande est adressée pour la construction d'une nouvelle église plus vaste ayant pratiquement la superficie des bâtiments existants, ce qui revenait à ne plus avoir de bâtiment à usage militaire à l’intérieur du fort. Grâce à l'appui du général Adolphe Niel, le comité des fortifications donne un avis favorable dans sa séance du 7 janvier 1852. L'autorisation de construire une nouvelle chapelle est donnée par le ministre de la guerre le 5 février 1852. Les études et la recherche du financement peuvent commencer.
Le 1er novembre 1852, Mgr Eugène de Mazenod sollicite des offrandes des fidèles. Des études sont demandées à différents architectes. Le conseil d'administration de la chapelle se réunit le 30 décembre 1852 en présence de Mgr de Mazenod. Le projet présenté par Léon Vaudoyer qui travaille à la cathédrale de la Major est le seul de style romano byzantin, tandis que les autres sont de style néogothique. Chaque projet recueille cinq voix, mais le vote du vicaire étant prépondérant, le projet de Vaudoyer est retenu. Les plans ont été en fait établis par Henri-Jacques Espérandieu, son élève âgé seulement de vingt trois ans.
Le 23 juin 1853 Espérandieu est nommé architecte et met au point le projet. Bien qu'étant protestant, il ne semble pas que sa religion fut une cause majeure des difficultés rencontrées avec la commission du sanctuaire chargée de la mise en œuvre des travaux. Celle-ci décida, sans consultation de l'architecte, de ne pas mettre les travaux en adjudication pour faire jouer la concurrence, mais de les confier le 9 août 1853 directement à Pierre Bérenger, entrepreneur et architecte de l'église Saint-Michel, qui avait lui-même proposé un des projets néogothiques et qui était un proche de Mgr Mazenod. La commission décide également de lui imposer le choix d'artistes tels que le sculpteur Joseph Marius Ramus ou le peintre Karl Müller de Düsseldorf sans se soucier de savoir si leurs œuvres s'adapteront à l'architecture retenue. Le choix de Karl Müller ne fut pas confirmé par la suite, ce qui permit à l'architecte de s'orienter vers une décoration de mosaïques.
La pose de la première pierre par l'évêque de Marseille Mgr Eugène de Mazenod a lieu le 11 septembre 1853. Les travaux commencent mais sont très pénibles à cause des fondations à faire dans une roche très dure, et des difficultés financières apparaissent rapidement. En 1855 on décide d’organiser une loterie autorisée par le gouvernement, mais qui rapporte moins que prévu. Les ressources financières sont d'autant plus insuffisantes que la commission du sanctuaire décide l'agrandissement de la crypte qui, au lieu de se trouver seulement sous le chœur, s'étendra sous toute la chapelle supérieure. Malgré un prêt engagé sur les biens propres de l’évêque, le chantier est arrêté deux ans de 1859 à 1861, année de la mort de Mgr Mazenod.
Le nouvel évêque Mgr Patrice Cruice qui arrive à la fin du mois d'août 1861, relance les travaux. La générosité de citoyens de toutes confessions et de toutes conditions sociales – de l'Empereur et de l'Impératrice qui rendent visite à la vierge de la Garde le 9 septembre 1860 au plus modeste des marseillais – permet l'achèvement des travaux.
La consécration du sanctuaire est donnée le samedi 4 juin 1864 par le cardinal Villecourt, membre de la curie romaine, en présence de quarante-trois autres évêques. En 1866, un dallage en mosaïque est posé dans l'église supérieure et le clocher carré est terminé ; le bourdon est installé en octobre de la même année.
En 1867, on construit sur le clocher carré un piédestal cylindrique ou campanile destiné à recevoir la statue monumentale de la vierge. Le financement de la statue est pris en charge par la ville de Marseille. Les esquisses de la statue faites par trois artistes parisiens, Eugène-Louis Lequesne, Aimé Millet et Charles Gumery sont examinées par un jury composé de l'architecte Espérandieu, de Bernex, maire de Marseille, Jeanron, directeur de l'école des Beaux-Arts, Bontoux, professeur à l'école de sculpture et Luce, président du Tribunal civil, administrateur du sanctuaire de Notre-Dame de la Garde. Le projet de Lequesne est retenu.
Pour des raisons de coût et de poids, le cuivre est retenu comme matière pour la confection de la statue. Une méthode toute nouvelle pour l'époque est adoptée pour la réalisation de la statue : la galvanoplastie, "cet art de mouler sans le secours du feu", est préférée au cuivre repoussé au marteau. En effet, selon un rapport scientifique du 19 novembre 1866, l'emploi du cuivre galvanique permet d'obtenir une reproduction irréprochable et une solidité qui ne laissera rien à désirer. Seul Viollet-Leduc pense que les produits de la galvanoplastie ne résisteront pas longtemps aux agents atmosphériques à Marseille. Espérandieu fait exécuter la statue en quatre tronçons à cause des difficultés de son ascension sur la colline et au sommet du clocher. Il insère au centre de la sculpture une flèche en fer, noyau d’un escalier à vis accédant à la tête de la Vierge pour l’entretien et la contemplation du site. Cette structure métallique, qui sert de support à la statue, permet de consolider l’ensemble en le reliant au gros œuvre de la tour. L'exécution de la statue, confiée aux ateliers Christofle, est terminée en août 1869. Pour réaliser cet ouvrage, il aura fallu utiliser des cuves d'électrolyse contenant 90 000 litres d'une solution de sulfate de cuivre et des moules en ronde bosse en gutta-percha armé pesant 1 500 kg. Les premiers éléments sont montés le 17 mai 1870 et la consécration est faite le 24 septembre 1870, mais sans éclat, la défaite face aux armées prussiennes occupant tous les esprits. Cette statue est dorée à la feuille ; la dorure qui nécessite 500 g. d’or a été refaite en 1897, 1936, 1963 et 1989.
En mars 1871 se forme à Marseille, à l’instigation de Gaston Crémieux, la Commune révolutionnaire. Aidés par des garibaldiens, les révolutionnaires s’emparent de la préfecture et font prisonnier le préfet. Le 26 mars 1871 le général Espivent de la Villeboisnet se replie à Aubagne, mais entreprend la reconquête de la ville dès le 3 avril. Les insurgés réfugiés dans la préfecture se trouvent sous le feu des batteries installées au fort Saint-Nicolas et à Notre-Dame de la Garde. Ils capitulent le 4 avril et disent que la Vierge a changé de nom et s’appelle désormais « Notre-Dame de la bombarde ».
À la suite du décès d’Espérandieu survenu le 11 septembre 1874, Henri Antoine Révoil est chargé du décor intérieur de la basilique, en particulier de la réalisation des mosaïques. La construction de l'autel majeur et la pose des mosaïques du chœur s'effectuent en 1882. Malheureusement un incendie survient le 5 juin 1884 et détruit l'autel et la mosaïque du chœur ; de plus la statue d'argent de la Vierge est endommagée. La statue et les mosaïques sont restaurées et l'autel reconstruit selon les plans de Révoil. Le 26 avril 1886 le cardinal Lavigerie consacre le nouvel autel.
En 1886, des stalles réalisées en noyer sont installées dans le chœur ; les dernières mosaïques des chapelles latérales sont posées de 1887 à 1892. En 1897, on met en place les deux portes de bronze de l'église supérieure et la mosaïque qui les surmonte ; la statue de la vierge est redorée pour la première fois. L'achèvement définitif de la basilique a donc lieu plus de quarante ans après la pose de la première pierre.