Dès 1660 le Chevalier de Clerville construit le fort Saint-Nicolas sur ordre de Louis XIV qui voulait tenir Marseille en respect en cas de rébellion. Auparavant, à cet emplacement se trouvait une tour servant à manoeuvrer la chaîne qui fermait l'entrée du port. Emportée comme trophée après le sac des Aragonnais, cette chaîne se trouve actuellement dans la cathédrale de Valence, en Espagne.
Sous le Second Empire, lors de la construction de la Résidence Impériale (le Pharo), le fort fut coupé en deux afin de créer une voie d'accès détruisant ainsi le symbole de l'autorité royale : côté mer le fort Saint-Nicolas qui accueille la garnison militaire et son mess des officiers, et côté terre le fort d'Entrecasteaux.
Le fort occupe un éperon calcaire compris entre le port, l'abbaye Saint-Victor et le Pharo. La construction enserra un moment la chapelle Saint-Nicolas construite au Moyen-Age, puis celle-ci fut détruite. Le fort est composé de deux ensembles étagés dont le plus bas, faisant office de basse cour sur le port est isolé depuis 1862 par le percement du boulevard (aujourd'hui Charles Livon).
Le haut-fort est formé de deux enceintes imbriquées dont le plan quadrangulaire s'accroche à l'escarpement. La qualité des maçonneries, grand appareil de calcaire rose de la Couronne, et de leur mise en oeuvre (chaînages d'angle à bossages et cordon créant des arabesques de contre-courbes dans les pentes) concourent à créer une impression de puissance sereine, caractéristique du style du Chevalier de Clerville.
Le fort est classé Monument Historique en 1969.
Depuis 2024, la Citadelle de Marseille est ouverte gratuitement au public.