Le bastion 21 est héritier d'une des redoutes de 1761 restaurée en 1794 et destinée à être remplacée dans le projet du général de Marecot de 1802 par un de ses forts détachés, dit "ouvrage C". L'ouvrage issu des travaux du Premier Empire est une lunette terrassée dont le réduit de gorge en maçonnerie n'est qu'ébauché.
L'ouvrage doit devenir un des bastions de l'enceinte du Palais dans les projets établis à partir des années 1820, selon différentes dispositions, mais toujours en conservant la forme générale de la lunette du Premier Empire. Les études, étroitement liées à celles de la courtine 21-22, sont compliquées par la topographie de ce secteur de la place.
Le bastion 21 sous sa forme actuelle est construit de 1862 à 1865, comprenant l'achèvement du réduit C. L'aménagement d'une poterne à la jonction avec la courtine 21-22 prévu dans la seconde moitié des années 1860 n'est jamais réalisé.
Les terrassements du bastion sont réaménagés à la fin du 19e siècle, vers 1880-1890.
