The castle was built in the reign of the boy-king Edward VI, but the fear that drove it back to his father's time. Henry VIII had built a chain of artillery forts around the south coast of England in the 1530s and 1540s - bold, low, thick-walled batteries designed to fire the newer long-range cannon at French invasion fleets. By 1547 those defences extended west to the Scilly Isles, where the Killigrew family had Royal connections and a personal interest in seeing the islands fortified. Construction at Tresco started in 1548 and continued through 1551 and 1552 under successive surveyors. Between 1548 and 1552, the Crown spent 3,123 pounds on Scilly's defences; a 1579 survey put the total cost including garrisons at 6,000 pounds. Edward's successor Mary I planned a garrison of 150 men but probably never achieved it. By 1558 Killigrew was styling himself 'captain in the Castell of Tresco'.

The castle is polygonal, built from local granite, with a gun battery at the front and a dining room, kitchen and living quarters behind. The plan is unusual for the period and survives elsewhere only in a few small blockhouses along the River Thames - none of which were exposed to the kind of weather that Castle Down catches. The fundamental problem was the elevation. Forty metres above sea level meant that even a heavy cannon fired from the parapet could only depress its barrel so far, and the guns simply could not be aimed at ships moving through the channel below. To compensate, a small blockhouse was probably built down by the water - on the same rocks where Cromwell's Castle would later stand - but the main fort itself was, militarily, almost useless from the moment it was finished.

During the English Civil War the Scilly Isles backed Charles I, and after a brief period in Parliamentary hands they rebelled in 1648 to support him. The Royalist garrison on Tresco believed - perhaps optimistically - that the castle on Castle Down was a critical defensive position, and they built new earthwork defences around it to protect against attack from the landward side. (Some scholars think those defences actually date from around 1627, built by the King's engineer Bernard Johnson.) The castle picked up its current name during this Royalist occupation. In April 1651 Admiral Robert Blake arrived with a Parliamentary task force, landed at Old Grimsby harbour on the other side of Tresco, and simply marched south past the castle - ignoring it entirely. Its commander, William Edgecumbe, retreated on 19 April and his men blew up part of the building as they went, leaving what remained to the Parliamentary colonel George Fleetwood.

Some of the stone from the demolished King Charles's Castle was almost certainly carried downhill and incorporated into the new Cromwell's Castle, which Blake's masons built at sea level over the following year. The exchange feels almost narrative: a Royalist fort blown up by its own defenders, repurposed by Parliamentary stonemasons into a Republican one. In 1660 Charles II was restored and Edward Sherburne came to Scilly to inspect the defences. He recommended repairs to King Charles's Castle, which was then being used to house soldiers, but no serious restoration appears to have happened. The antiquary William Borlase visited in 1752 and dismissed the building as labour without skill. By the end of the eighteenth century the writer John Troutbeck was praising the thickness of the walls but reaching the same conclusion: the fort was useless for what it had been built to do.

In 1922 the lease of the castle passed to Arthur Dorrien-Smith of Tresco Abbey, who handed it - along with several other Tresco properties - to the Ministry of Works. In 1954 the site was partially excavated, uncovering coins, pottery and a buckle, and parts of the first floor of the battery were rebuilt from fallen stonework dug out of the rubble. What you see today is what survived. A large room on the west side, facing the sea, originally held the battery with embrasures for five guns. Two small bedrooms, each 2.9 metres square, lead off the main hall. A guardroom 3.5 metres square forms the entrance. The walls survive in places up to 3.4 metres high and 1.65 metres thick, though they average half that. It is impossible to be certain whether the castle was originally two storeys throughout or just at the gun battery, with the accommodation as a single-storey wing. English Heritage controls the site today, and it is open to visitors year-round.