Offiziell begann der Bau der Feste Kaiser Alexander am 3. September 1816. Grundlage war – wie bei der Feste Kaiser Franz in Lützel – ein Entwurf des Festungsingenieurs Claudius Franz Le Bauld de Nans. Ihren Namen erhielt die Anlage im Zuge eines Besuchs des preußischen Königs Friedrich Wilhelm III. am 24. November 1818 – zu Ehren des russischen Zaren Alexander I.
1822 wurden Teile der Festung mit Truppen belegt, zwei Jahre später war alles fertig.
1831 wurde schließlich die unterirdischen Verbindungsgang zum Fort Großfürst Konstantin beendet.