De bouw van Kastellet startte in 1626 in opdracht van Christiaan IV van Denemarken, die een loopgraaf liet graven in het noordelijke deel van de verdedigingsmuur van Kopenhagen. Hoewel Christiaan grootse plannen had voor een eigen kasteel in Kastellet, moest hij deze wegens verslechterde economische omstandigheden laten varen. Zijn opvolger Frederik III zette het werk voort. Na de Zweedse belegering van Kopenhagen van 1658 tot 1660 riep Frederik de hulp in van de Hollandse ingenieur Henrick Ruse om het vestingwerk te herstellen en uit te breiden. De koning liet de vesting uitroepen tot Citadellet Frederikshavn ("De citadel van Frederikshavn"), maar deze naam werd al snel vervormd tot Kastellet ("de citadel").

Kastellet speelde in 1807 een rol in de verdediging van Kopenhagen tegen Engeland tijdens de Slag om Kopenhagen.

De Deense schilder Christen Købke (1810–1848) groeide op in Kastellet en maakte een aantal schilderijen van het gebied.

Van 1989 tot 1999 werd heel Kastellet gerenoveerd met geld uit het fonds van A.P. Møller en zijn vrouw Chastine McKinney Møllers.