La construction du fort Saint-Nicolas répond à un programme global de fortification des grands ports du royaume qui comprend la défense de la ville, le développement du port, la création d'un arsenal. Après la participation de la ville de Marseille aux révoltes de la Fronde, le roi confit en 1660 au chevalier de Clerville, commissaire général des fortifications du royaume le projet de citadelle. Le site choisi accueille déjà une chapelle Saint-Nicolas dépendant de l'abbaye de Saint-Victor. En 1663 le Haut-fort, site dit fort d'Entrecasteaux, est construit, complété en 1664 par le Bas-Fort, site dit fort Ganteaume. Le système défensif comprend une seconde citadelle sur l'autre rive du port, le fort Saint-Jean (1668 à 1671), une nouvelle enceinte urbaine et un arsenal des galères.

L'ensemble fortifié est visité en 1679 par Vauban dont l'avis est très critique. Il le manifeste dans son projet de défense de Marseille rédigé en 1701. Le fort tient lieu de caserne et de prison. En 1790, une partie du front est est démolie par la population. Ce secteur du mur d'enceinte est rétabli en 1833. En 1864, la création du boulevard de l’Empereur (actuel boulevard Charles Livon) isole les deux forts. Entre1859 et 1863, est construit en contrebas des remparts du fort d'Entrecasteaux la caserne militaire Saint Victor (actuelle caserne d’Aurelle. Un monument commémoratif de la Seconde guerre est établi dans l'ancien moulin en 1954 . Le fort Saint-Nicolas est classé en totalité par un arrêté du 14 janvier 1969.

Le fort d’Entrecasteaux a été cédé en décembre 2010 par le ministère de la Défense à la Ville de Marseille. Depuis 2003 le Haut-Fort est restauré par l'association ACTA VISTA dans le cadre de chantiers de formation aux métiers du patrimoine : remparts est, nord, et ouest (600 ml), demi-lune de Villeroy (poudrière), demi-lune Dauphine et Bastion de Beringhen.